POJ 2653 Pick-up sticks解题报告

一、问题描述

二、解题思路

判断线段相交的方法见算法导论

三、代码

 

#include<iostream>
using namespace std;
const double eps=1e-8;
int dcmp(double x)
{
    if(x<-eps)
        return -1;
    else
        return (x>eps);
}
struct Point
{
    double x;
    double y;
};
struct Line
{
    Point p1;
    Point p2;
};
double dmax(double a,double b)
{
    return a>b?a:b;
}
double dmin(double a,double b)
{
    return a>b?b:a;
}
double direction(Point p1,Point p2,Point p3)
{
    return (p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y);
}
//p3是否在p1,p2之间

bool on_segment(Point p1,Point p2,Point p3)
{
    double xmin=dmin(p1.x,p2.x);
    double xmax=dmax(p1.x,p2.x);
    double ymin=dmin(p1.y,p2.y);
    double ymax=dmax(p1.y,p2.y);
    if( xmin <= p3.x && xmax >= p3.x && ymin<=p3.y && ymax>=p3.y)
        return true;
    else
        return false;

}
bool segment_intersect(Point p1,Point p2,Point p3,Point p4)
{
    double d1,d2,d3,d4;
    d1=direction(p3,p4,p1);
    d2=direction(p3,p4,p2);
    d3=direction(p1,p2,p3);
    d4=direction(p1,p2,p4);
    if( ((d1>0 && d2<0)||(d1<0 && d2>0))
        && ((d3>0 && d4<0)||(d3<0 && d4>0)))
        return true;
    else
        if(d1==0 && on_segment(p3,p4,p1))
            return true;
        else
            if(d2==0 && on_segment(p3,p4,p2))
                return true;
            else
                if(d3==0 && on_segment(p1,p2,p3))
                    return true;
                else
                    if(d4==0 && on_segment(p1,p2,p4))
                        return true;
                    else
                        return false;
}
int N;
Line L[100005];
int main()
{
    int i,j;
    //bool flag;

    int cnt;
    while(scanf("%d",&N)!=EOF)
    {
        if(N==0)
            break;
        for(i=1;i<=N;++i)
            scanf("%lf%lf%lf%lf",&L[i].p1.x,&L[i].p1.y,&L[i].p2.x,&L[i].p2.y);
        printf("Top sticks: ");
        cnt=0;
        for(i=1;i<N;++i)
        {
            for(j=i+1;j<=N;++j)
            {
                if(segment_intersect(L[i].p1, L[i].p2, L[j].p1, L[j].p2))
                {
                    break;
                }
            }
            if(j==(N+1))
            {
                printf("%d, ",i);
                cnt++;
            }
            if(cnt==999)
                break;
        }
        printf("%d.\n",N);
    }

    return 0;
}