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

望大神指点错哪儿了。

Posted by 14310120133 at 2016-08-26 10:05:28 on Problem 2079
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct point
{
    int x;
    int y;
} p[50010];
int cross(point a,point b,point c)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp1(point a,point b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
bool cmp2(point a,point b)
{
    if(cross(a,b,p[0])>0)
        return true;
    if(cross(a,b,p[0])<0)
        return false;
    if(cross(a,b,p[0])==0)
        dis(a,p[0])-dis(b,p[0])<=0?true:false;
}
int main()
{
    int n;
    point s[50010];
    while(scanf("%d",&n)&&n!=-1)
    {
        for(int i=0; i<n; i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        if(n<=2)
        {
            printf("0.00\n");
            continue;
        }
        sort(p,p+n,cmp1);
        sort(p+1,p+n,cmp2);
        memset(s,0,sizeof(s));
        s[0]=p[0];
        s[1]=p[1];
        int top=1;
        for(int i=2; i<n; i++)
        {
            while(i>=1&&cross(p[i],s[top],s[top-1])>=0)
                top--;
            s[++top]=p[i];
        }
        if(n<=2)
        {
            printf("0.00\n");
            continue;
        }
        s[++top]=p[0];
        int ans=0;
        for(int i=0; i<top; i++)
        {
            int q=1;
            for(int j=i+1; j<=top; j++)
            {
                while(cross(s[i],s[j],s[q+1])>cross(s[i],s[j],s[q]))
                    q=(q+1)%top;
                ans=max(ans,cross(s[i],s[j],s[q]));
            }
        }
        double res=double(ans/2.0);
        printf("%.2lf\n",res);
    }
    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