POJ 2079 凸包最大内接三角形

Description

Input

Output

Sample Input

3
3 4
2 6
2 7
5
2 6
3 9
2 0
8 0
6 5
-1

Sample Output

0.50
27.00

经典题目：

代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/10 16:26:51
File Name :20.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){
	if(fabs(x)<eps)return 0;
	return x>0?1:-1;
}
struct Point{
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;y=_y;
	}
};
Point operator + (const Point &a,const Point &b){  
    return Point(a.x+b.x,a.y+b.y);  
}  
Point operator - (const Point &a,const Point &b){  
    return Point(a.x-b.x,a.y-b.y);  
}  
Point operator * (const Point &a,const double &p){  
    return Point(a.x*p,a.y*p);  
}  
Point operator / (const Point &a,const double &p){  
    return Point(a.x/p,a.y/p);  
}  
bool operator < (const Point &a,const Point &b){  
    return a.x<b.x||(a.x==b.x&&a.y<b.y);  
}  
bool operator == (const Point &a,const Point &b){  
    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;  
}  
double Dot(Point  a,Point b){  
    return a.x*b.x+a.y*b.y;  
}  
double Length(Point a){  
    return sqrt(Dot(a,a));  
}  
double Angle(Point a,Point b){  
    return acos(Dot(a,b)/Length(a)/Length(b));  
}  
double angle(Point a){  
    return atan2(a.y,a.x);  
}  
double Cross(Point a,Point b){  
    return a.x*b.y-a.y*b.x;  
}  
Point vecunit(Point a){  
    return a/Length(a);  
}  
Point Normal(Point a){  
    return Point(-a.y,a.x)/Length(a);  
}  
Point Rotate(Point a,double rad){  
    return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));  
}  
double Area2(Point a,Point b,Point c){  
    return Length(Cross(b-a,c-a));  
}  
double DistanceToSegment(Point p, Point a, Point b)  {  
    if(a == b) return Length(p-a);  
    Point v1 = b-a, v2 = p-a, v3 = p-b;  
    if(dcmp(Dot(v1, v2)) < 0) return Length(v2);  
    else if(dcmp(Dot(v1, v3)) > 0) return Length(v3);  
    else return fabs(Cross(v1, v2)) / Length(v1);  
}  
double dis_pair_seg(Point p1, Point p2, Point p3, Point p4)  {  
    return min(min(DistanceToSegment(p1, p3, p4), DistanceToSegment(p2, p3, p4)),  
     min(DistanceToSegment(p3, p1, p2), DistanceToSegment(p4, p1, p2)));  
}  
vector<Point> CH(vector<Point> p){
	sort(p.begin(),p.end());
	p.erase(unique(p.begin(),p.end()),p.end());
	int n=p.size();
	int m=0;
	vector<Point> ch(n+1);
	for(int i=0;i<n;i++){
		while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-1])<=0)m--;
		ch[m++]=p[i];
	}
	int k=m;
	for(int i=n-2;i>=0;i--){
		while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
		ch[m++]=p[i];
	}
	if(n>1)m--;
	ch.resize(m);
	return ch;
}
double RC_Distance(vector<Point> ch1,vector<Point> ch2)  
{  
    int q=0, p=0,n=ch1.size(),m=ch2.size();
    for(int i=0;i<n;i++) if(ch1[i].y-ch1[p].y < -eps) p=i;  
    for(int i=0;i<m;i++)if(ch2[i].y-ch2[q].y > eps) q=i;  
    ch1.push_back(ch1[0]);ch2.push_back(ch2[0]); 
  
    double tmp, ans=1e100;  
    for(int i=0;i<n;i++) 
    {  
        while((tmp = Cross(ch1[p+1]-ch1[p], ch2[q+1]-ch1[p]) - Cross(ch1[p+1]-ch1[p], ch2[q]- ch1[p])) > eps)  
            q=(q+1)%m;  
        if(tmp < -eps) ans = min(ans,DistanceToSegment(ch2[q],ch1[p],ch1[p+1]));  
        else ans = min(ans,dis_pair_seg(ch1[p],ch1[p+1],ch2[q],ch2[q+1]));  
        p=(p+1)%n;  
    }  
    return ans;  
}  
double RC_Triangle(vector<Point> res)// 凸包最大内接三角形  
{  
	 int n=res.size();
     if(n<3)    return 0;  
     double ans=0, tmp;  
     res.push_back(res[0]);
     int j, k;  
     for(int i=0;i<n;i++)
     {  
         j = (i+1)%n;  
         k = (j+1)%n;  
         while((j != k) && (k != i))  
         {  
              while(Cross(res[j] - res[i], res[k+1] - res[i]) > Cross(res[j] - res[i], res[k] - res[i])) k= (k+1)%n;  
              tmp = Cross(res[j] - res[i], res[k] - res[i]);if(tmp > ans) ans = tmp;  
              j = (j+1)%n;  
         }  
     }  
     return ans/2;  
}  

int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n,m;
	 while(cin>>n&&n!=-1){
		 vector<Point> res;
		 Point p;
		 while(n--)scanf("%lf%lf",&p.x,&p.y),res.push_back(p);
		 res=CH(res);
		 printf("%.2lf\n",RC_Triangle(res));
	 }
     return 0;
}

POJ 2079 凸包最大内接三角形,布布扣,bubuko.com

POJ 2079 凸包最大内接三角形

原文：http://blog.csdn.net/xianxingwuguan1/article/details/25496715