bzoj1069 SCOI2007 最大土地面积

时间：2023-03-08 16:55:22

1069: [SCOI2007]最大土地面积

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2560  Solved: 983

Description

　　在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成
的多边形面积最大。

Input

　　第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

Output

　　最大的多边形面积，答案精确到小数点后3位。

Sample Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1.000

HINT

数据范围 n<=2000, |x|,|y|<=100000

先求个凸包，然后枚举对角线，两边找面积最大的三角形

 /*by SilverN*/
 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<cstring>
 #include<algorithm>
 #define ll long long
 using namespace std;
 ;
 struct P{
     double x,y;
 }p[mxn],s[mxn];
 ;
 int n;
 ;
 //
 inline P operator - (P a,P b){
     P t; t.x=a.x-b.x; t.y=a.y-b.y; return t;
 }
 inline double operator * (P a,P b){
     return (a.x*b.y)-(b.x*a.y);
 }
 inline double dis(P a,P b){
     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
 }
 inline bool operator < (P a,P b){
     ])*(b-p[]);
     )])<dis(b,p[]);
     ;
 }
 //
 void graham(){
     ;
     int i,j;
     ;i<=n;i++){
         if(p[i].y<p[t].y || (p[i].y==p[t].y && p[i].x<p[t].x))t=i;
     }
     swap(p[],p[t]);
     sort(p+,p+n+);
     s[++top]=p[];s[++top]=p[];
     ;i<=n;i++){
          && (p[i]-s[top-])*(s[top]-s[top-])<=)
             top--;
         s[++top]=p[i];
     }
     s[top+]=p[];
     return;
 }
 double solve()
 {
     s[top+]=p[];
     ;
     int a,b;
     ;x<=top;x++)
     {
         a=x%top+;b=(x+)%top+;
         ;y<=top;y++)
         {
             !=y&&(s[y]-s[x])*(s[a+]-s[x])>(s[y]-s[x])*(s[a]-s[x]))
                 a=a%top+;
             !=x&&(s[b+]-s[x])*(s[y]-s[x])>(s[b]-s[x])*(s[y]-s[x]))
                 b=b%top+;
             ans=max((s[y]-s[x])*(s[a]-s[x])+(s[b]-s[x])*(s[y]-s[x]),ans);//(s[b]-s[x])*(s[y]-s[x])前后颠倒成(s[y]-s[x])*(s[b]-s[x])就会WA，不能理解
         }
     }
     return ans;
 }
 int main(){
     scanf("%d",&n);
     int i,j;
     ;i<=n;i++){
         scanf("%lf%lf",&p[i].x,&p[i].y);
     }
     graham();
     printf();
     ;
 }

相关文章