嘻嘻嘻嘻，从读题到过题大概一个小时？
这套题题面太长了。。。就挑短的写。。
题意很简单。 给出平面上n个点，求一个面积最小的平行四边形覆盖这n个点。
显然要先求凸包。
然后枚举边就可以了。我一开始脑子抽了，只枚举了相邻的。。(今天下午四点多才吃上早饭很痛苦。感觉神智不清，昨晚补题补到3点。。。)
然后我们要 分别找出 离这两条边最远的 点吧，然后通过简单的平移操作求直线交点，再用叉积搞一下就阔以了。
虽然理论上 n^3不会t，但我还是t了。。。所以我们先预处理出来离每条边最远的点是哪一个。就阔以了。
记得特判一下没有凸包的情况，虽然不知道有没有这种数据。。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef double db; 4 const db eps=1e-6; 5 const db pi=acos(-1); 6 int sign(db k){ 7 if (k>eps) return 1; else if (k<-eps) return -1; return 0; 8 } 9 int cmp(db k1,db k2){return sign(k1-k2);} 10 struct point{ 11 db x,y; 12 point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} 13 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} 14 point operator * (db k1) const{return (point){x*k1,y*k1};} 15 point operator / (db k1) const{return (point){x/k1,y/k1};} 16 db abs(){return sqrt(x*x+y*y);} 17 db dis(point k1){return ((*this)-k1).abs();} 18 point turn90(){ return point{-y,x};} 19 db getP()const { return sign(y)==1||(sign(y)==0&&sign(x)==-1);} 20 point unit(){db w=abs(); return point{x/w,y/w};} 21 db abs2(){return x*x+y*y;} 22 bool operator < (const point k1) const{ 23 int a=cmp(x,k1.x); 24 if (a==-1) return 1; else if (a==1) return 0; else return cmp(y,k1.y)==-1; 25 } 26 }; 27 db cross(point k1,point k2){ return k1.x*k2.y-k1.y*k2.x;} 28 db dot(point k1,point k2){ return k1.x*k2.x+k1.y*k2.y;} 29 db rad(point k1,point k2){ return atan2(cross(k1,k2),dot(k1,k2));} 30 int compareangle(point k1,point k2){ 31 return k1.getP()<k2.getP()||(k1.getP()==k2.getP()&&sign(cross(k1,k2))>0); 32 } 33 point proj(point k1,point k2,point q){ // q 到直线 k1,k2 的投影 34 point k=k2-k1; return k1+k*(dot(q-k1,k)/k.abs2()); 35 } 36 point getLL(point k1,point k2,point k3,point k4){ 37 db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); 38 return (k1*w2+k2*w1)/(w1+w2); 39 } 40 struct line{ 41 point p[2]; 42 line(point k1,point k2){p[0]=k1;p[1]=k2;} 43 point &operator[](int k){ return p[k];} 44 int include(point k){ return sign(cross(p[1]-p[0],k-p[0])>0);} 45 point dir(){ return p[1]-p[0];} 46 line push(db eps){//向左手边平移eps 47 //const db eps=1e-6; 48 point delta=(p[1]-p[0]).turn90().unit()*eps; 49 return {p[0]-delta,p[1]-delta}; 50 } 51 }; 52 point getLL(line k1,line k2){ 53 return getLL(k1[0],k1[1],k2[0],k2[1]); 54 } 55 int parallel(line k1,line k2){ return sign(cross(k1.dir(),k2.dir()))==0;} 56 int sameDir(line k1,line k2){ 57 return parallel(k1,k2)&&sign(dot(k1.dir(),k2.dir()))==1; 58 } 59 int operator <(line k1,line k2){ 60 if(sameDir(k1,k2))return k2.include(k1[0]); 61 return compareangle(k1.dir(),k2.dir()); 62 } 63 int checkpos(line k1,line k2,line k3){ return k3.include(getLL(k1,k2));} 64 vector<point> convexHull(vector<point>ps){ 65 int n = ps.size();if(n<=1)return ps; 66 sort(ps.begin(),ps.end()); 67 vector<point> qs(n*2);int k=0; 68 for(int i=0;i<n;qs[k++]=ps[i++]) 69 while (k>1&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])<=0)--k; 70 for(int i=n-2,t=k;i>=0;qs[k++]=ps[i--]) 71 while (k>t&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])<=0)--k; 72 qs.resize(k-1); 73 return qs; 74 } 75 int t,n; 76 vector<point> p;point s1,t1,s2,t2; 77 map<pair<int,int>,int> mp; 78 db check(int a,int b,int c,int d){ 79 int id1=mp[make_pair(a,b)],id2=mp[make_pair(c,d)]; 80 s1=p[id1],s2=p[id1]+p[a]-p[b]; 81 point t1 = getLL(p[c],p[d],s1,s2);//一个交点 82 s1 = p[id2],s2=p[id2]+p[c]-p[d]; 83 point t2 = getLL(p[a],p[b],s1,s2); 84 point bb = getLL(p[a],p[b],p[c],p[d]); 85 db S = abs(cross(bb-t1,bb-t2)); 86 return S; 87 } 88 void init(){ 89 int m = p.size(); 90 for(int i=0;i<m;i++){ 91 db mx = 0;int id=-1; 92 for(int j=0;j<m;j++){ 93 db tmp = p[j].dis(proj(p[i],p[(i+1)%m],p[j])); 94 if(cmp(tmp,mx)>0){ 95 mx=tmp,id=j; 96 } 97 } 98 mp[make_pair(i,(i+1)%m)]=id; 99 } 100 } 101 point tmp; 102 int main(){ 103 scanf("%d",&t); 104 for(int cas=1;cas<=t;cas++){ 105 scanf("%d",&n); 106 for(int i=0;i<n;i++){ 107 scanf("%lf%lf",&tmp.x,&tmp.y); 108 p.push_back(tmp); 109 } 110 p=convexHull(p); 111 if(p.size()<3){ 112 printf("Swarm %d Parallelogram Area: 0.0000 ",cas); 113 continue; 114 } 115 init(); 116 db ans = 1e15; 117 int m = p.size(); 118 for(int i=0;i<m;i++){ 119 for(int j=i+1;j<m;j++) { 120 ans = min(ans,check(i, (i + 1) % m, j,(j+1)%m)); 121 } 122 } 123 printf("Swarm %d Parallelogram Area: %.4f ",cas,ans); 124 p.clear();mp.clear(); 125 } 126 } 127 /** 128 1 129 4 130 0 0 131 0 1 132 0 2 133 0 3 134 */