| ||||||||||
| 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 | |||||||||
本地运行官方数据没问题,但是提交就是WA......#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<map>
using namespace std;
double eps=1e-8,ans;
double res[]={
2.0000000,
1.4966630,
-1,
8.5293611,
0.9648614,
2.4358621,
3.5369064,
0.8676061,
0.5163210,
1.0932113,
7.7705678,
3.1865100,
-1,
8.0226154,
-1,
21.1419939,
2.8655059,
2.0961204,
2.7251605,
4.4695445,
6.3285463,
-1,
13.8037361,
0.3883676,
4.4062551,
6.7138469,
2.8955617,
26.8204177,
1.1856118,
-1,
-1,
3.8021499,
6.8071058,
4.8242181,
5.4204496,
3.9591100,
2.6426620,
4.0339260,
3.5349495,
1.3356397,
1.9926927,
1.9251430,
6.4152631,
2.9756773,
15.0473405,
1.9875230,
0.8210476,
-1,
4.0420922,
1.0102691,
4.3716062,
10.9763761,
3.8947346,
1.8071569,
1.8279691,
4.5856980,
1.5606357,
2.4223391,
10.7298981,
4.3556521,
2.0947586,
-1,
-1,
1.5671191,
-1,
-1,
1.3931094,
-1,
-1,
1.3218469,
1.6128374,
1.4994759,
14.3576046,
4.1171894,
27.1524679,
6.2725005,
2.9471415,
16.1373439,
5.9907579,
2.4632939,
3.6372158,
11.1660912,
-1,
2.8191673,
3.2433597,
2.7810744,
23.9393462,
8.2731867,
3.0439581,
3.5321219,
-1,
3.3059329,
6.4154676,
-1,
1.3287114,
3.3952692,
3.5521327,
6.8687006,
4.2566122,
4.5732251,
-1,
9.0606291,
5.6768616,
-1
};
struct point
{
double x,y;
};
point a[3],nw1[3],nw2[3],adj[80100][201];
int num[80100];
double comarea(double x1,double y1,double x2,double y2,double x3,double y3)
{
return fabs((y2-y1)*x3-(x2-x1)*y3+x2*y1-x1*y2)/2.0;
}
bool inter(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
{
double ru1,ru2,A,B;
A=(y2-y1)*(x4-x3)-(x2-x1)*(y4-y3);
B=(y3-y1)*(x4-x3)-(x3-x1)*(y4-y3);
if(fabs(A)<eps)
return false;
ru1=B/A;
B=(y3-y1)*(x2-x1)-(x3-x1)*(y2-y1);
ru2=B/A;
if(ru1<1-eps&&ru1>eps&&ru2<1-eps&&ru2>eps)
return true;
return false;
}
bool overlap(point nw1[],point nw2[])
{
int i,j;
double x,y,value;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(inter(nw1[i].x,nw1[i].y,nw1[(i+1)%3].x,nw1[(i+1)%3].y,nw2[j].x,nw2[j].y,nw2[(j+1)%3].x,nw2[(j+1)%3].y))
return true;
}
x=(nw1[0].x+nw1[1].x+nw1[2].x)/3.00;
y=(nw1[0].y+nw1[1].y+nw1[2].y)/3.00;
value=comarea(x,y,nw2[0].x,nw2[0].y,nw2[1].x,nw2[1].y);
value+=comarea(x,y,nw2[1].x,nw2[1].y,nw2[2].x,nw2[2].y);
value+=comarea(x,y,nw2[0].x,nw2[0].y,nw2[2].x,nw2[2].y);
if(fabs(value-comarea(nw2[0].x,nw2[0].y,nw2[1].x,nw2[1].y,nw2[2].x,nw2[2].y))<eps)
return true;
x=(nw2[0].x+nw2[1].x+nw2[2].x)/3.00;
y=(nw2[0].y+nw2[1].y+nw2[2].y)/3.00;
value=comarea(x,y,nw1[0].x,nw1[0].y,nw1[1].x,nw1[1].y);
value+=comarea(x,y,nw1[1].x,nw1[1].y,nw1[2].x,nw1[2].y);
value+=comarea(x,y,nw1[0].x,nw1[0].y,nw1[2].x,nw1[2].y);
if(fabs(value-comarea(nw1[0].x,nw1[0].y,nw1[1].x,nw1[1].y,nw1[2].x,nw1[2].y))<eps)
return true;
return false;
}
int main()
{
int i,j,s,p,q,cnt,zhi,tst=0;
double A,B,x0,y0,x1,y1,x2,y2,x,y,z,value,len,v1,v2,v,aa,bb,cc,zz;
while(true)
{
for(i=0;i<3;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
if(a[0].x==0&&a[0].y==0&&a[1].x==0&&a[1].y==0&&a[2].x==0&&a[2].y==0)
break;
memset(num,0,sizeof(num));
for(x1=-100;x1<=100;x1++)
for(y1=-100;y1<=100;y1++)
{
zhi=(int)((x1-a[2].x)*(x1-a[2].x)+(y1-a[2].y)*(y1-a[2].y));
adj[zhi][num[zhi]].x=x1;
adj[zhi][num[zhi]++].y=y1;
}
cnt=0;
ans=1000000000;
for(x0=-100;x0<=100;x0+=1)
for(y0=-100;y0<=100;y0+=1)
{
if((a[2].y-y0)*(a[1].x-x0)>(a[2].x-x0)*(a[1].y-y0)-eps)
continue;
value=(x0-a[2].x)*(x0-a[2].x)+(y0-a[2].y)*(y0-a[2].y);
zhi=(int)value;
for(int ii=0;ii<num[zhi];ii++)//for(x1=xmin;x1<=xmax;x1+=1)
{
x1=adj[zhi][ii].x;
y1=adj[zhi][ii].y;
if((a[2].y-y1)*(a[0].x-x1)<(a[2].x-x1)*(a[0].y-y1)+eps)
continue;
v1=(x0-a[1].x)*(x0-a[1].x)+(y0-a[1].y)*(y0-a[1].y);
v2=(x1-a[0].x)*(x1-a[0].x)+(y1-a[0].y)*(y1-a[0].y);
v=a[0].x*a[0].x-a[1].x*a[1].x+a[0].y*a[0].y-a[1].y*a[1].y+v1-v2;
aa=(2*a[0].x-2*a[1].x)*sqrt(v1);
bb=(2*a[0].y-2*a[1].y)*sqrt(v1);
cc=v-(2*a[0].x-2*a[1].x)*a[1].x-(2*a[0].y-2*a[1].y)*a[1].y;
v=cc/sqrt(aa*aa+bb*bb);
if(fabs(v-1)<eps)
v=1;
if(fabs(v+1)<eps)
v=-1;
if(v<-1||v>1)
continue;
double theta,phi;
phi=acos(aa/sqrt(aa*aa+bb*bb));
if(bb<0)
phi=-phi;
for(j=0;j<2;j++)
{
if(j==0)
theta=phi+acos(v);
else
theta=phi-acos(v);
x2=a[1].x+sqrt(v1)*cos(theta);
y2=a[1].y+sqrt(v1)*sin(theta);
if(!(fabs(x2-(int)x2)<eps)&&!((fabs(x2-(int)(x2+1)))<eps)&&!(fabs(x2-(int)(x2-1))<eps))
continue;
if(!(fabs(y2-(int)y2)<eps)&&!((fabs(y2-(int)(y2+1)))<eps)&&!(fabs(y2-(int)(y2-1))<eps))
continue;
if((a[0].y-y2)*(a[1].x-x2)<(a[1].y-y2)*(a[0].x-x2)+eps)
continue;
if(x2>100+eps||x2<-100-eps||y2>100+eps||y2<-100-eps)
continue;
for(s=0;s<3;s++)
nw1[s]=a[s];
nw1[0].x=x0;
nw1[0].y=y0;
for(s=0;s<3;s++)
nw2[s]=a[s];
nw2[1].x=x1;
nw2[1].y=y1;
if(overlap(nw1,nw2))
continue;
for(s=0;s<3;s++)
nw1[s]=a[s];//nw1=a;
nw1[2].x=x2;
nw1[2].y=y2;
if(overlap(nw1,nw2))
continue;
for(s=0;s<3;s++)
nw2[s]=a[s];//nw2=a;
nw2[0].x=x0;
nw2[0].y=y0;
if(overlap(nw1,nw2))
continue;
double l1,l2,l3;
l1=(x2-a[0].x)*(x2-a[0].x)+(y2-a[0].y)*(y2-a[0].y);
l2=(x0-a[1].x)*(x0-a[1].x)+(y0-a[1].y)*(y0-a[1].y);
l3=(x0-a[2].x)*(x0-a[2].x)+(y0-a[2].y)*(y0-a[2].y);
A=2*((a[1].x-a[0].x)*(a[2].y-a[1].y)-(a[2].x-a[1].x)*(a[1].y-a[0].y));
double orz1=a[1].x*a[1].x-a[0].x*a[0].x+a[1].y*a[1].y-a[0].y*a[0].y;
double orz2=a[2].x*a[2].x-a[1].x*a[1].x+a[2].y*a[2].y-a[1].y*a[1].y;
B=(l1-l2+orz1)*(a[2].y-a[1].y)-(l2-l3+orz2)*(a[1].y-a[0].y);
x=B/A;
A=-A;
B=(l1-l2+orz1)*(a[2].x-a[1].x)-(l2-l3+orz2)*(a[1].x-a[0].x);
y=B/A;
z=l1-(x-a[0].x)*(x-a[0].x)-(y-a[0].y)*(y-a[0].y);
if(z<eps)
continue;
z=sqrt(z);
if(ans>z)
ans=z;
}
}
}
if(ans==1000000000)
{
ans=-1;
puts("-1");
}
else
printf("%.7lf\n",ans);
while(fabs(ans-res[tst])>1e-6)
puts("orz");
tst++;
}
return 0;
}
res[]存放的是官方数据的答案,
while(fabs(ans-res[tst])>1e-6)
puts("orz");
验证结果是否正确,在自己本地运行所有的官方数据都是对的,但提交上去就是OLE,不知道肿么回事,求教~~
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator