
5 1 1 4 2 2 3 3 1 1 -2.0 8 4 1 4 8 2 3 3 6 -2.0 3 0 0 1 1 1 0 2 1 2 0 3 1 0
Top sticks: 2, 4, 5. Top sticks: 1, 2, 3.
#include <stdio.h>
#define MAX 100100
struct Point{
double x ,y ;
Point operator-(Point p)
{
Point ans ;
ans.x = x-p.x ;
ans.y = y-p.y ;
return ans ;
}
};
struct Segment{
Point s , e ;
bool cover ;
}seg[MAX];
double min(double x , double y)
{
return x>y?y:x ;
}
double max(double x , double y)
{
return x>y?x:y ;
}
bool quickExclude(const Segment &a , const Segment &b)
{
double minRX = min(a.s.x,a.e.x) , minRY = min(a.s.y,a.e.y) ;
double maxRX = max(a.s.x,a.e.x) , maxRY = max(a.s.y,a.e.y) ;
double minTX = min(b.s.x,b.e.x) , minTY = min(b.s.y,b.e.y) ;
double maxTX = max(b.s.x,b.e.x) , maxTY = max(b.s.y,b.e.y) ;
if(max(minTX,minRX)>min(maxTX,maxRX) && max(minTY,minRY)>min(maxTY,maxRY))
{
return false ;
}
return true ;
}
double f(Point p1 , Point p2)
{
return p1.x*p2.y-p1.y*p2.x ;
}
bool ifIntersect(Segment &a , Segment &b)
{
if(quickExclude(a,b))
{
if(f(a.s-b.s,b.e-b.s)*f(b.e-b.s,a.e-b.s)>=0 &&
f(b.s-a.s,a.e-a.s)*f(a.e-a.s,b.e-a.s)>=0 )
{
return true ;
}
}
return false ;
}
int main()
{
int n ;
while(~scanf("%d",&n) && n)
{
for(int i = 0 ; i < n ; ++i)
{
scanf("%lf%lf%lf%lf",&seg[i].s.x,&seg[i].s.y,&seg[i].e.x,&seg[i].e.y) ;
seg[i].cover = false ;
}
for(int i = 0 ; i < n ; ++i) //注意只能这样写!!下面有超时的代码例子
{
for(int j = i+1 ; j < n ; ++j)
{
if(ifIntersect(seg[i],seg[j]))
{
seg[i].cover = true ;
break ;
}
}
}
/* 超时的代码!!!
for(int i = 0 ; i < n ; ++i)
{
for(int j = i+1 ; j < n ; ++j)
{
if(!seg[i].cover)
{
if(ifIntersect(seg[i],seg[j]))
{
seg[i].cover = true ;
break ;
}
}
}
}
*/
int i = 0;
for(i = 0 ; i < n ; ++i)
{
if(!seg[i].cover)
{
printf("Top sticks: %d",i+1) ;
break ;
}
}
for(i=i+1; i < n ; ++i)
{
if(!seg[i].cover)
{
printf(", %d",i+1) ;
}
}
puts(".") ;
}
return 0 ;
}hdu 1147 Pick-up sticks 判断线段相交 ~~ 注意判断顺序!!不然容易超时
原文:http://blog.csdn.net/lionel_d/article/details/44172839