首页 > 代码库 > HDU 2202 最大三角形

HDU 2202 最大三角形

2024-07-24 06:50:59   218人阅读

 

最大三角形

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3248    Accepted Submission(s): 1098


Problem Description
老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。
 

 

Input
输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.
 

 

Output
对于每一组测试数据，请输出构成的最大的三角形的面积，结果保留两位小数。
每组输出占一行。
 

 

Sample Input
33 42 63 762 63 92 08 06 67 7
 

 

Sample Output
1.5027.00

 

给你 n 个点 然后求其中三个点形成的三角形面积最大为多少 。 

解法就是求一个凸包 ， 然后 n^3 枚举凸包栈里面的点求一下向量叉积就过了 -。- 

 

 

#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;typedef pair<double,double> Point;const int N = 50010 ;//#define x first//#define y second//vector<Point>ch , p;int n ;struct node{    double x , y ;    node(){};    node( double a ,double b ){ x = a , y = b ; }    node operator - (const node &a )const{ return node(x - a.x , y - a.y ); }}p[N] , ch[N];inline double Cross( node a , node b ){ return a.x * b.y - a.y * b.x ; }inline bool cmp ( const node &a ,const node &b ){ if(a.x != b.x )return a.x < b.x ; else return a.y < b.y ; }int ConvexHull(){    int  top = 0 ;    sort( p , p + n , cmp );    for( int i = 0 ; i < n ; ++ i ){        while( top > 1 && Cross( ch[top-2] - ch[top-1] , p[i] - ch[top-2 ] ) <= 0  ) top -- ;        ch[top++] = p[i];    }    int k = top ;    for( int i = n-2 ; i >= 0 ; --i ){        while( top > k && Cross( ch[top-2] - ch[top-1 ] , p[i]- ch[top -2 ]) <= 0 )top -- ;        ch[top++ ] = p[i];    }    if( n > 1 ) top -- ;    return  top ;}void run(){    double a , b ;    for( int i = 0 ; i < n ; ++ i ){        cin >> p[i].x >> p[i].y ;    }    int m = ConvexHull();    double ans = 0 ;    for( int i = 0 ; i < m ; ++i ){        for( int j = i + 1 ; j < m ; ++j ){            for( int k = j + 1 ; k < m ; ++k ){                ans = max ( ans , fabs ( Cross( ch[i] - ch[j] , ch[i] - ch[k] ) ) );            }        }    }    printf("%.2lf\n", 0.5 * ans  );}int main(){    ios::sync_with_stdio(false);    while( cin >> n && n ) run();}

 

HDU 2202 最大三角形


联系
我们