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

本地运行官方数据没问题,但是提交就是WA......

Posted by Los_Angelos_Laycurse at 2012-04-27 21:19:49 on Problem 3520
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator