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

Why WA

Posted by sazuki at 2008-06-05 01:24:55 on Problem 3587
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Point
{
    double x,y;
}p[660];
int i,j,k,u,n,T,tot,l[660];
double a,b,c,s,S,r,max;
int sort_f(const void *A,const void *B);
main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);max=0;
        for(i=0;i<n;i++)
           scanf("%lf %lf",&p[i].x,&p[i].y);
        for(i=0;i<n;i++)
        {
          tot=0;
          for(j=0;j<n;j++)
          {
              if(i==j) continue;
              l[tot]=j;tot++;
          }
          qsort(l,tot,sizeof(int),sort_f);l[tot]=l[0];
          for(u=0;u<tot;u++)
          {
              j=l[u];k=l[u+1];
              a=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
              b=sqrt((p[i].x-p[k].x)*(p[i].x-p[k].x)+(p[i].y-p[k].y)*(p[i].y-p[k].y));
              c=sqrt((p[k].x-p[j].x)*(p[k].x-p[j].x)+(p[k].y-p[j].y)*(p[k].y-p[j].y));
              s=(a+b+c)/2;S=sqrt(s*(s-a)*(s-b)*(s-c));
              r=(a*b*c)/(4*S);if(r>max) max=r;
          }
        }    
        printf("%.3lf\n",max);
    }
}

int sort_f(const void *A,const void *B)
{
    double X1,X2,Y1,Y2,Z;
    X1=p[*(int *)A].x-p[i].x;X2=p[*(int *)B].x-p[i].x;
    Y1=p[*(int *)A].y-p[i].y;Y2=p[*(int *)B].y-p[i].y;
    Z=X1*Y2-Y1*X2;
    if(Z<0) return -1;
    if(Z>0) return  1;
    return 0;
}

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