作者在 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;
}
//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;
}