凸包,

#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> typedef long double ld; const int maxn = 100100; int n; struct T{ld x,y;inline T(ld a=0,ld b=0){x=a,y=b;}inline T& operator += (const T&b){x+=b.x,y+=b.y;return *this;}inline T& operator += (const ld&b){x+=b,y+=b;return *this;}inline T& operator -= (const T&b){x-=b.x,y-=b.y;return *this;}inline T& operator -= (const ld&b){x-=b,y-=b;return *this;}inline T& operator *= (const ld&b){x*=b,y*=b;return *this;}inline T& operator /= (const ld&b){x/=b,y/=b;return *this;}inline T operator + (const T&b)const{return T(x+b.x,y+b.y);}inline T operator - (const T&b)const{return T(x-b.x,y-b.y);}inline T operator / (const ld&b)const{return T(x/b,y/b);}inline T operator * (const ld&b)const{return T(x*b,y*b);} }a[maxn]; inline ld cross(T a,T b){return a.x*b.y-a.y*b.x;} inline ld cross(T a,T b,T c){return cross(b-a,c-a);} const auto cmp = [](T a,T b){ld res=cross(a,b);return res!=0?res<0:a.x<b.x; }; T st[maxn]; int top; inline void up(ld&a,ld b){if(a<b)a=b;} int main(){std::ios::sync_with_stdio(false),std::cin.tie(0);std::cin >> n;int mn=1;for(int i=1;i<=n;++i){std::cin >> a[i].x >> a[i].y;if(a[i].y<a[mn].y||a[i].y==a[mn].y&&a[i].x<a[mn].x)mn=i;}std::swap(a[mn],a[1]);T p = a[mn];for(int i=1;i<=n;++i)a[i]-=p;std::sort(a+2,a+n+1,cmp);for(int i=1;i<=n;++i){st[++top]=a[i];while(top>2&&cross(st[top-2],st[top-1],st[top])>=0)st[--top]=a[i];}ld ans=fabs(cross(st[1],st[2],st[3]))/2;for(int a=1;a<=top;++a){for(int c=a+2,b=a+1,d=c%top+1;d!=a&&c<=top;++c){while(cross(st[a],st[c],st[b%top+1])>cross(st[a],st[c],st[b]) && b%top+1 != c)b=b%top+1;while(cross(st[a],st[c],st[d%top+1])<cross(st[a],st[c],st[d]) && d%top+1 != a)d=d%top+1;up(ans,fabsl(cross(st[a],st[c],st[b])+fabsl(cross(st[a],st[c],st[d]))));}}printf("%.3Lf",ans/2); }

?

轉載于:https://www.cnblogs.com/skip1978/p/10353761.html

總結

以上是生活随笔為你收集整理的[SCOI2007]最大土地面积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。