Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 找到我的程序WA的原因你就AC了!用C写的

Posted by omllyf at 2009-08-17 17:58:59 on Problem 3304
```#include<stdio.h>
#include<string.h>
#include<math.h>
#define mini 0.00000001
typedef struct
{
double x,y;
}point;
struct
{
point p[2];
}line[10000];
double max(double a,double b);
double min(double a,double b);
int onsegment(point p,point p1,point p2);
int direction(point p1,point p0,point p2);
int segmentsintersection(point p1,point p2,point p3,point p4);
double distance(double x1,double y1,double x2,double y2);
int main()
{
int test,n,i,j,k,t,q,flag;
double px1,px2,py1,py2;
point p1,p2;
scanf("%d",&test);
while(test--)
{
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%lf%lf%lf%lf",&line[i].p[0].x,&line[i].p[0].y,&line[i].p[1].x,&line[i].p[1].y);
if(n==1||n==2)printf("Yes!\n");
else
{
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
for(k=0;k<=1;k++)
{
for(t=0;t<=1;t++)
{
px1=line[i].p[k].x;py1=line[i].p[k].y;
px2=line[j].p[t].x;py2=line[j].p[t].y;
if(distance(px1,py1,px2,py2)>=mini)
{
flag=1;
p1.x=px1;p1.y=py1;
p2.x=px2;p2.y=py2;
for(q=0;q<n;q++)
{
if(!segmentsintersection(p1,p2,line[q].p[0],line[q].p[1]))
{
flag=0;
break;
}
}
if(flag)
{
goto omllyf;
}
}
}
}
}
}
omllyf:	if(flag)printf("Yes!\n");
else printf("No!\n");
}
}
return 0;
}
int direction(point p1,point p0,point p2)
{
double temp=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
if(temp>mini)return 1;
if(temp<-mini)return -1;
return 0;
}
int segmentsintersection(point p1,point p2,point p3,point p4)
{
int d1,d2,d3,d4;
d1=direction(p3,p4,p1);
d2=direction(p3,p4,p2);
d3=direction(p1,p2,p3);
d4=direction(p1,p2,p4);
if(d1*d2<0&&d3*d4<0)return 1;
if(!d1&&onsegment(p1,p3,p4))return 1;
if(!d2&&onsegment(p2,p3,p4))return 1;
if(!d3&&onsegment(p3,p1,p2))return 1;
if(!d4&&onsegment(p4,p1,p2))return 1;
return 0;
}
int onsegment(point p,point p1,point p2)
{
if(p.x>=min(p1.x,p2.x)&&p.x<=max(p1.x,p2.x)&&p.y>=min(p1.y,p2.y)&&p.y<=max(p1.y,p2.y))return 1;
return 0;
}
double max(double a,double b){if(a>b)return a;return b;}
double min(double a,double b){if(a<b)return a;return b;}
double distance(double x1,double y1,double x2,double y2)
{
double temp;
temp=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
return temp;
}```

Followed by: