题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版题目:http://paste.ubuntu.com/18378190/
数据传送门:http://pan.baidu.com/s/1skSFZxr
哎呀,本来想着终于可以A题了!结果又被卡常QAQ,然后又只有60分QAQ
正解就是凸包+旋转卡壳+乱搞,然而原教的代码完全没有几何库,全部写进代码%%%%%%%,因此他天生自带小常数啊!
原教 Orz:http://paste.ubuntu.com/18378298/
哎呀,不想卡常了,贴一份代码水过就算了吧
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int MAXN = 8000+9; const double EPS = 1e-8; const double INF = 1e30; double vout; int n; inline int cmp(double x){if (fabs(x)<EPS) return 0; else return (x>0)?1:-1;} struct Point{ double x,y; inline bool operator < (const Point &A) const {return (x < A.x) || (x == A.x && y < A.y);} inline bool operator == (const Point &A) const {return !cmp(x-A.x) && !cmp(y-A.y);} inline Point operator + (const Point &A) {Point tmp;tmp.x=x+A.x;tmp.y=y+A.y;return tmp;} inline Point operator - (const Point &A) {Point tmp;tmp.x=x-A.x;tmp.y=y-A.y;return tmp;} }p[MAXN],TMP[MAXN],ori[MAXN],SIZE[MAXN]; typedef Point Vector; inline double Cross(Vector A, Vector B){return A.x*B.y - A.y*B.x;} inline double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);} inline bool Onleft(Point A, Point B, Point C){return cmp(Area2(A,B,C)) > 0;} inline void CalArea(Point *A){ A[5] = A[1]; double ret = 0; for (int i=1;i<=4;i++) ret += Cross(A[i],A[i+1]); vout = max(vout, fabs(ret)); } inline int ConvexHull(Point *A, int N){ sort(A+1,A+1+N); int cnt=0; for (int i=1;i<=N;i++){ while (cnt > 1 && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--; TMP[++cnt] = A[i]; } for (int i=N-1,lim=cnt;i;i--){ while (cnt > lim && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--; TMP[++cnt] = A[i]; } if (cnt==4 && N==4) { for (int i=1,tag;i<=4;i++){ tag = 0; for (int j=1;j<cnt;j++) if (A[i] == TMP[j]) tag = 1; if (!tag) {A[4]=A[i];break;} } } for (int i=1;i<cnt;i++) A[i] = TMP[i]; return cnt-1; } inline void update(Point *A){ if (ConvexHull(A,4) == 4) CalArea(A); else { double sa = fabs(Area2(A[1],A[2],A[3])); double mn = INF; A[5] = A[4]; A[4] = A[1]; for (int i=1;i<=3;i++) mn = min(mn, fabs(Area2(A[i],A[i+1],A[5]))); if (vout < sa-mn) vout = max(vout, sa-mn); } } inline void cycle(int N){ for (int i=1;i<=N;i++) p[i+N] = p[i]; for (int i=1;i<=N;i++) p[i+N*2] = p[i]; for (int k=2;k<N;k++){ for (int i=1,itr1=2,itr2=i+k+1;i<=N;i++){ while (itr1 < i+k && fabs(Area2(p[i],p[itr1],p[i+k])) <= fabs(Area2(p[i],p[itr1+1],p[i+k]))) itr1++; while (itr2 < i+N && fabs(Area2(p[i+k],p[itr2],p[i])) <= fabs(Area2(p[i+k],p[itr2+1],p[i]))) itr2++; SIZE[1] = p[i]; SIZE[2] = p[itr1]; SIZE[3] = p[i+k]; SIZE[4] = p[itr2]; CalArea(SIZE); } } } int main(){ freopen("large.in","r",stdin); freopen("large.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y), ori[i] = p[i]; int tmp = ConvexHull(p,n); if (tmp == 4) CalArea(p); else if (tmp == 3) for (int i=1;i<=n;i++){ int t = 1; for (int j=1;j<=3;j++) if (p[j]==ori[i]) t=0; if (t) p[4] = ori[i], update(p); } else cycle(tmp); printf("%.3lf",vout/2.0); return 0; }
唯一比较欣慰的,快4个月没有写过几何题了,居然还能写出来,还没怎么调试就过了。