| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
表示数据超弱,一遍暴力AC!!#include<iostream> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define eps 1e-8 const int Max=100001; const int NUM=1001; int num[NUM]; using namespace std; int sign(double x) { return (x>eps)-(x<-eps); } typedef struct Node { double x; double y; }point; 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); } //相交返回true,否则为false,接口为两线段的端点 bool IsIntersected(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(s1,s2,e1)*multi(s1,e1,e2)>0)&&(multi(s2,s1,e2)*multi(s2,e2,e1)>0); } typedef struct Segment { point s; point e; }segment; segment s[Max]; int main() { int n,m,i,j,p; while(cin>>n&&n) { memset(num,0,sizeof(num)); m=0; for(i=1;i<=n;i++) { cin>>s[i].s.x>>s[i].s.y>>s[i].e.x>>s[i].e.y; } for(i=1;i<n;i++) { p=0; for(j=i+1;j<=n;j++) { if(IsIntersected(s[i].s,s[i].e,s[j].s,s[j].e)) { p=1; break; } } if(p==0) num[m++]=i; } num[m]=n; cout<<"Top sticks: "; for(i=0;i<=m;i++) { if(i==m) cout<<num[i]<<"."<<endl; else cout<<num[i]<<", "; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator