pku2653

作者在 2010-07-30 18:12:07 发布以下内容
 http://acm.pku.edu.cn/JudgeOnline/problem?id=2653
//with 1 <= n <= 100000, the number of sticks for this case
//these numbers are the planar coordinates of the endpoints of one stick
// You may assume that there are no more than 1000 top sticks

#include<iostream>
#include<cmath>
using namespace std;
struct point
{   double x,y;  };
//计算叉积
double multi(point p0,point p1,point p2)
{   return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
//判断线段相交
bool is_cross(point s1,point e1,point s2,point e2)
{
   return max(s1.x,e1.x)>=min(s2.x,e2.x)&&
          max(s2.x,e2.x)>=min(s1.x,e1.x)&&
          max(s1.y,e1.y)>=min(s2.y,e2.y)&&
          max(s2.y,e2.y)>=min(s1.y,e1.y)&&
          multi(s2,e1,s1)*multi(e1,e2,s1)>=0&&
          multi(s1,e2,s2)*multi(e2,e1,s2)>=0;
}
#define max 100005
point s[max],e[max];
int main()
{
    long n,i,j,k;
    long ans[1005];
    while(scanf("%ld",&n),n)
    {
        for(i=1;i<=n;i++)
           scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&e[i].x,&e[i].y);
        k=1;        
        for(i=n;i>1;i--)
        {  
            for(j=n;j>i;j--)
              if(is_cross(s[i],e[i],s[j],e[j]))break;
            if(j!=i)continue;
            for(j=i-1;j>0;j--)
            {
               if(is_cross(s[i],e[i],s[j],e[j])){ ans[k++]=i; break;}            
            }
            if(j==0)ans[k++]=i;
        }
        for(i=2;i<=n;i++)
           if(is_cross(s[1],e[1],s[i],e[i]))break;
        if(i==n+1)ans[k++]=1;
        printf("Top sticks: %ld",ans[k-1]);
        for(i=k-2;i>0;i--)
          printf(", %ld",ans[i]);
        printf(".\n");
    }
    system("pause");
    return 0;
}

 
计算几何 | 阅读 781 次
文章评论,共0条
游客请输入验证码
最新评论