Problem 2 圈地(land.cpp/c/pas) 【題目描述】 2維平面上有n個木樁，你有一次圈地的機會並得到圈到的土地，為了體現你的高風亮節，你要使你圈到的土地面積盡量小。圈地需要圈一個至少3個點的多邊形，多邊形的頂點就是一個木樁，圈得的土地就是這個多邊形內部的土地。 【輸入格式】 第一行一個整數n，表示木樁個數。 接下來n行，每行2個整數表示一個木樁的坐標，坐標兩兩不同。 【輸出格式】 僅一行，表示最小圈得的土地面積，保留2位小數。 【樣例輸入】 樣例1： 3 0 0 0 1 1 0 樣例2： 4 0 0 0 1 0 2 1 1 【樣例輸出】 樣例1： 0.50 樣例2： 0.00 【數據范圍】 對於10%的數據，n<=100； 對於30%的數據，n<=300； 對於50%的數據，n<=500； 對於100%的數據，n<=1000。 顯然這題的多邊形一定是三角形。 首先求出所有邊，按k排序（必須先求出來，不能直接在排序的時候求） 然後考慮這些邊，會發現正好是繞坐標系旋轉一圈。 也就是說如果按照以這邊為y軸從左至右排序，那麼每轉移一條邊，只需要調換該邊2個點的位置 這題沒給范圍，但是必須用long long [cpp] #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<functional> #include<iostream> #include<cmath> using namespace std; #define MAXN (1000+10) #define INF (1000000000) #define eps 1e-10 struct P { int x,y; long long operator*(const P &b) { return (long long)x*b.y-(long long)b.x*y; } friend bool operator<(P a,P b){if (a.x^b.x) return a.x<b.x;return a.y<b.y;} }a[MAXN]; long long abs2(long long x){if (x>0) return x;return -x;} int n,h[MAXN]; struct E { int i,j; double k; E(){} E(int _i,int _j):i(_i),j(_j){if (a[i].x==a[j].x) k=1e10;else k=(double)(a[i].y-a[j].y)/(a[i].x-a[j].x);} friend bool operator<(E a,E b){return a.k<b.k; } }e[MAXN*MAXN/2]; long long S2(P A,P B,P C) { return abs2(A*B+B*C+C*A); } int size=0; int main() { freopen("land.in","r",stdin); freopen("land.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); long long ans=(long long)1<<60; /* for (int i=1;i<=n-2;i++) for (int j=i+1;j<n;j++) for (int k=j+1;k<=n;k++) ans=min(ans,abs2(a[i]*a[j]+a[j]*a[k]+a[k]*a[i])); */ sort(a+1,a+1+n); for (int i=1;i<=n;i++) h[i]=i; for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) { e[++size]=E(i,j); } sort(e+1,e+1+size); for (int i=1;i<=size&&ans;i++) { if (h[e[i].i]>1&&h[e[i].i]<n) ans=min(ans,S2(a[h[e[i].i]-1],a[h[e[i].i]],a[h[e[i].i]+1])); if (h[e[i].j]>1&&h[e[i].j]<n) ans=min(ans,S2(a[h[e[i].j]-1],a[h[e[i].j]],a[h[e[i].j]+1])); swap(a[h[e[i].i]],a[h[e[i].j]]); swap(h[e[i].i],h[e[i].j]); } printf("%.2lf",(double)ans/2); return 0; }
