| ||||||||||
| 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