POJ 2653 Pick-up sticks(线段规范相交)

POJ 2653 Pick-up sticks(线段规范相交)

http://poj.org/problem?id=2653

题意: ZOJ2551

有n根厚度忽略不计的木棍平行的往地板按顺序扔,扔完之后给你每根木棍在地板这个二维平面的端点坐标,要你输出那些木棍是在最上面的(即没有任何一根木棍压着它).

用例的图,木棍2压着木棍1了.

分析:

本题直接暴力解决即可.由于木棍是按顺序扔下去的,那么只要在当前木棍后面扔的所有木棍都是有可能压着它的. 所以我们依次遍历当前木棍之后放的所有木棍即可.

(判断木棍是否被压,只要看这两个木棍是否规范相交即可)

用的依然是刘汝佳 线段规范相交的模板.

这个貌似不能优化的,

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}

struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x, A.y-B.y);
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)
{
    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
    double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}

const int maxn=100000+5;
int n;
Point P[maxn],Q[maxn];
bool up[maxn];//标记该线段是否在最上面

int main()
{
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=1;i<=n;++i) scanf("%lf%lf%lf%lf",&P[i].x,&P[i].y,&Q[i].x,&Q[i].y),up[i]=true;

        for(int i=1;i<=n;++i)
        {
            for(int j=i+1;j<=n;++j)
            if(SegmentProperIntersection(P[i],Q[i],P[j],Q[j]))
            {
                up[i]=false;
                break;
            }
        }
        int i;
        for(i=1;i<=n;++i)if(up[i])break;
        printf("Top sticks: %d",i);
        for(++i;i<=n;++i)if(up[i]) printf(", %d",i);
        printf(".\n");
    }
    return 0;
}