判断线段相交的方法 先判断直线是否相交 再判断点是否在线段上 复杂度是常数的
题目保证最后答案小于1000
故从后往前尝试用后面的线段 "压"前面的线段 排除不可能的答案 就可以轻松AC了。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std; const double eps=1e-9; int cmp(double x)
{
if(fabs(x)<eps)return 0;
if(x>0)return 1;
else return -1;
} const double pi=acos(-1.0); inline double sqr(double x)
{
return x*x;
} struct point
{
double x,y;
point (){}
point (double a,double b):x(a),y(b){}
void input()
{
scanf("%lf%lf",&x,&y);
}
friend point operator +(const point &a,const point &b)
{
return point(a.x+b.x,a.y+b.y);
}
friend point operator -(const point &a,const point &b)
{
return point(a.x-b.x,a.y-b.y);
}
friend bool operator ==(const point &a,const point &b)
{
return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
}
friend point operator *(const point &a,const double &b)
{
return point(a.x*b,a.y*b);
}
friend point operator*(const double &a,const point &b)
{
return point(a*b.x,a*b.y);
}
friend point operator /(const point &a,const double &b)
{
return point(a.x/b,a.y/b);
}
double norm()
{
return sqrt(sqr(x)+sqr(y));
}
}; double det(const point &a,const point &b)
{
return a.x*b.y-a.y*b.x;
} double dot(const point &a,const point &b)
{
return a.x*b.x+a.y*b.y;
} double dist(const point &a,const point &b)
{
return (a-b).norm();
} point rotate_point(const point &p,double A)
{
double tx=p.x,ty=p.y;
return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
} struct line
{
point a,b;
line(){};
line(point x,point y):a(x),b(y)
{ }
}; bool parallel(line a,line b)
{
return !cmp(det(a.a-a.b,b.a-b.b));
} bool line_joined(line a,line b,point &res)
{
if(parallel(a,b))return false;
double s1=det(a.a-b.a,b.b-b.a);
double s2=det(a.b-b.a,b.b-b.a);
res=(s1*a.b-s2*a.a)/(s1-s2);
return true;
} bool pointonSegment(point p,point s,point t)
{
return cmp(det(p-s,t-s))==0&&cmp(dot(p-s,p-t))<=0;
} const int maxn=100000+1;
line li[maxn];
deque<int>q;
deque<int>qq;
int main()
{freopen("t.txt","r",stdin);
//freopen("1.txt","w",stdout);
int n;
while(scanf("%d",&n))
{
while(!q.empty())q.pop_front();
while(!qq.empty())qq.pop_front();
if(n==0)return 0;
for(int i=1;i<=n;i++)
{
point a,b;
a.input();b.input();
li[i]=line(a,b); q.push_back(i);
}
for(int i=n;i>1;i--)
{
while(!q.empty())
{ int nv=q.front();
if(nv>=i)break;
line nl=li[nv];q.pop_front();
point jo;
if(!line_joined(nl,li[i],jo)){qq.push_back(nv);continue;}
if((pointonSegment(jo,nl.a,nl.b))&&(pointonSegment(jo,li[i].a,li[i].b)))continue;
qq.push_back(nv);
}
while(!qq.empty())
{
int nv=qq.back();qq.pop_back();
q.push_front(nv);
}
}
printf("Top sticks: ");
while(!q.empty())
{
int now=q.front();q.pop_front();
if(q.empty())printf("%d.",now);
else printf("%d, ",now);
}
printf("\n");
}
return 0;
}