| ||||||||||
| 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<cstdio>
#include<cmath>
#define x first
#define y second
using namespace std;
const double EPS=1e-8;
int n,t;
pair<double,double> s[210];
double Max(double a,double b)
{
if(a>b) return a;
else return b;
}
double Min(double a,double b)
{
if(a<b) return a;
else return b;
}
bool judge(int a,int b,int c,int d)
{
if(((s[b].x-s[a].x)*(s[c].y-s[a].y)-(s[b].y-s[a].y)*(s[c].x-s[a].x))*((s[b].x-s[a].x)*(s[d].y-s[a].y)-(s[b].y-s[a].y)*(s[d].x-s[a].x))>EPS) return 0;
else return 1;
}
double dis(int a,int b)
{
return sqrt((s[a].x-s[b].x)*(s[a].x-s[b].x)+(s[a].y-s[b].y)*(s[a].y-s[b].y));
}
bool check(int a,int b)
{
if(dis(a,b)<EPS) return 0;
for(int i=1;i<=n;i++)
{
if(!judge(a,b,i*2-1,i*2)) return 0;
}
return 1;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&s[i*2-1].x,&s[i*2-1].y,&s[i*2].x,&s[i*2].y);
}
int flag=0;
for(int i=1;i<2*n;i++)
{
for(int j=i+1;j<=2*n;j++)
{
if(check(i,j))
{
flag=1;
break;
}
}
if(flag) break;
}
if(flag) printf("Yes!\n");
else printf("No!\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator