首页 > 代码库 > POJ2653 Pick-up sticks 判断线段相交
POJ2653 Pick-up sticks 判断线段相交
POJ2653
判断线段相交的方法 先判断直线是否相交 再判断点是否在线段上 复杂度是常数的
题目保证最后答案小于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; }
POJ2653 Pick-up sticks 判断线段相交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。