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了无数次才发现,三角形边可以不是凸包上的边~~Orz啊~~~~

Posted by ecjtu_yuweiwei at 2014-08-07 16:34:52 on Problem 2079
/*
题意:平面上给出n个点,然后其中任意三个点能组成三角形,求出最大的三角形面积
先求一次凸包,然后在凸包上枚举三角形的第一个顶点i,把其他两个顶点拿来旋转(旋转卡壳模板)。
此题要考虑到三角形的边可以不是凸包上的边
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
#define LL long long
#define IT __int64
#define zero(x) fabs(x)<eps
#define mm(a,b) memset(a,b,sizeof(a))
const int INF=0x7fffffff;
const double inf=1e8;
const double eps=1e-10;
const double PI=acos(-1.0);
const int Max=100000;
using namespace std;
int sign(double x)
{
    return (x>eps)-(x<-eps);
}
typedef struct Node
{
    double x;
    double y;
    Node(const double &_x=0, const double &_y=0) : x(_x), y(_y) {}
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    void output()
    {
        printf("%lf %lf\n",x,y);
    }
} point;
point list[Max],stack[Max];
int n;
int top;

int cnt;
int curcnt;
double xmult(point p0,point p1,point p2)
{
	return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dmult(point p0,point p1,point p2)
{
	return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
double Distance(point p1,point p2)// 返回两点之间欧氏距离
{
	return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );
}
bool cmp(point p1,point p2)
{
    double temp;
    temp=xmult(list[0],p1,p2);
    if(temp>0)
        return true;
    if(temp==0&&(Distance(list[0],p1)<Distance(list[0],p2)))
        return true;
    return false;
}
void convex_hull()//凸包模板
{
    int i;
    for(i=1; i<n; i++)
    {
        point temp;
        if((list[i].y<list[0].y)||(list[i].y==list[0].y&&list[i].x<list[0].x))
            swap(list[0],list[i]);
    }
    sort(list+1,list+n,cmp);
    top=1;
    stack[0]=list[0];
    stack[1]=list[1];
    for(i=2; i<n; i++)
    {
        while(top>=1&&xmult(stack[top-1],stack[top],list[i])<=0)
            top--;
        top++;
        stack[top]=list[i];
    }
}
double rotating_calipers()//旋转卡壳
{
    int i,j=1,k=2;
    double ans=0;
    stack[++top]=stack[0];
    for(i=0; i<top; i++)
    {
        //cout<<fabs(xmult(stack[p],stack[p+1],stack[q]))<<" "<<fabs(xmult(stack[p],stack[p+1],stack[q+1]))<<endl;
        //while(xmult(stack[p],stack[p+1],stack[q+1])>xmult(stack[p],stack[p+1],stack[q]))
            //q=(q+1)%top;
        //ans=max(ans,max(fabs(xmult(stack[p],stack[p+1],stack[q])),fabs(xmult(stack[p],stack[p+1],stack[q+1]))));
        //cout<<ans<<endl;
        /*开始没考虑边上的两点可以不是凸包上的点,WA无数次顿时发觉*/
        while(fabs(xmult(stack[(k+1)%n],stack[i],stack[j]))>fabs(xmult(stack[k],stack[i],stack[j])))
            k=(k+1)%n;
        while(fabs(xmult(stack[k],stack[i],stack[(j+1)%n]))>fabs(xmult(stack[k],stack[i],stack[j])))
            j=(j+1)%n;
        ans=max(ans,fabs(xmult(stack[k],stack[i],stack[j])));
    }
    return ans;
}
int main()
{
    int m,i,j;
    double area;
    while(cin>>n&&n>=0)
    {
        for(i=0;i<n;i++)
        {
            list[i].input();
        }
        convex_hull();
        //cout<<top<<endl;
        area=rotating_calipers();
        printf("%.2lf\n",area/2);
    }
    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