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