題意（中問(wèn)題直接粘吧）
矩形面積


Problem Description
小度熊有一個(gè)桌面，小度熊剪了很多矩形放在桌面上，小度熊想知道能把這些矩形包圍起來(lái)的面積最小的矩形的面積是多少。
?


Input
第一行一個(gè)正整數(shù) T，代表測(cè)試數(shù)據(jù)組數(shù)(1≤T≤20)，接下來(lái) T 組測(cè)試數(shù)據(jù)。


每組測(cè)試數(shù)據(jù)占若干行，第一行一個(gè)正整數(shù) N(1≤N<≤1000)，代表矩形的數(shù)量。接下來(lái) N 行，每行 8 個(gè)整數(shù)x1,y1,x2,y2,x3,y3,x4,y4，代表矩形的四個(gè)點(diǎn)坐標(biāo)，坐標(biāo)絕對(duì)值不會(huì)超過(guò)10000。


?


Output
對(duì)于每組測(cè)試數(shù)據(jù)，輸出兩行：


第一行輸出"Case #i:"，i 代表第 i 組測(cè)試數(shù)據(jù)。
第二行包含1 個(gè)數(shù)字，代表面積最小的矩形的面積，結(jié)果保留到整數(shù)位。


?


Sample Input
2
2
5 10 5 8 3 10 3 8
8 8 8 6 7 8 7 6
1
0 0 2 2 2 0 0 2
?


Sample Output
Case #1:
17
Case #2:
4


思路：

? ? ? 矩形不是凸出來(lái)的東西，吐出來(lái)的部分肯定是點(diǎn)，怎么連接邊都在點(diǎn)連線的里面，這樣就是求n*4個(gè)點(diǎn)的最小矩形覆蓋面積，直接來(lái)個(gè)模板就行了，一開(kāi)始用自己以前寫(xiě)的一個(gè)三分的方法來(lái)旋轉(zhuǎn)角度去求，一直wa,感覺(jué)那個(gè)只能求正方形吧，這個(gè)是在網(wǎng)上找的，還有第一次暴棧了，記得加上外掛開(kāi)戰(zhàn)的那個(gè)東西。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<math.h> #include<stdio.h> #include<string.h> #include<algorithm>using namespace std;typedef double typev; const double eps = 1e-8; const int N = 50005; int sign(double d){return d < -eps ? -1 : (d > eps); } struct point{typev x, y;point operator-(point d){point dd;dd.x = this->x - d.x;dd.y = this->y - d.y;return dd;}point operator+(point d){point dd;dd.x = this->x + d.x;dd.y = this->y + d.y;return dd;} }ps[N];//int n, cn; double dist(point d1, point d2){return sqrt(pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0)); } double dist2(point d1, point d2){return pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0); } bool cmp(point d1, point d2){return d1.y < d2.y || (d1.y == d2.y && d1.x < d2.x); } //st1-->ed1叉乘st2-->ed2的值 typev xmul(point st1, point ed1, point st2, point ed2){return (ed1.x - st1.x) * (ed2.y - st2.y) - (ed1.y - st1.y) * (ed2.x - st2.x); } typev dmul(point st1, point ed1, point st2, point ed2){return (ed1.x - st1.x) * (ed2.x - st2.x) + (ed1.y - st1.y) * (ed2.y - st2.y); } //多邊形類 struct poly{static const int N = 50005; //點(diǎn)數(shù)的最大值point ps[N+5]; //逆時(shí)針存儲(chǔ)多邊形的點(diǎn),[0,pn-1]存儲(chǔ)點(diǎn)int pn; //點(diǎn)數(shù)poly() { pn = 0; }//加進(jìn)一個(gè)點(diǎn)void push(point tp){ps[pn++] = tp;}//第k個(gè)位置int trim(int k){return (k+pn)%pn;}void clear(){ pn = 0; } }; //返回含有n個(gè)點(diǎn)的點(diǎn)集ps的凸包 poly graham(point* ps, int n){sort(ps, ps + n, cmp);poly ans;if(n <= 2){for(int i = 0; i < n; i++){ans.push(ps[i]);}return ans;}ans.push(ps[0]);ans.push(ps[1]);point* tps = ans.ps;int top = -1;tps[++top] = ps[0];tps[++top] = ps[1];for(int i = 2; i < n; i++){while(top > 0 && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;tps[++top] = ps[i];}int tmp = top; //注意要賦值給tmp！for(int i = n - 2; i >= 0; i--){while(top > tmp && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;tps[++top] = ps[i];}ans.pn = top;return ans; } //求點(diǎn)p到st->ed的垂足，列參數(shù)方程 point getRoot(point p, point st, point ed){point ans;double u=((ed.x-st.x)*(ed.x-st.x)+(ed.y-st.y)*(ed.y-st.y));u = ((ed.x-st.x)*(ed.x-p.x)+(ed.y-st.y)*(ed.y-p.y))/u;ans.x = u*st.x+(1-u)*ed.x;ans.y = u*st.y+(1-u)*ed.y;return ans; } //next為直線(st,ed)上的點(diǎn)，返回next沿(st,ed)右手垂直方向延伸l之后的點(diǎn) point change(point st, point ed, point next, double l){point dd;dd.x = -(ed - st).y;dd.y = (ed - st).x;double len = sqrt(dd.x * dd.x + dd.y * dd.y);dd.x /= len, dd.y /= len;dd.x *= l, dd.y *= l;dd = dd + next;return dd; } //求含n個(gè)點(diǎn)的點(diǎn)集ps的最小面積矩形，并把結(jié)果放在ds(ds為一個(gè)長(zhǎng)度是4的數(shù)組即可,ds中的點(diǎn)是逆時(shí)針的)中，并返回這個(gè)最小面積。 double getMinAreaRect(point* ps, int n, point* ds){int cn, i;double ans;point* con;poly tpoly = graham(ps, n);con = tpoly.ps;cn = tpoly.pn;if(cn <= 2){ds[0] = con[0]; ds[1] = con[1];ds[2] = con[1]; ds[3] = con[0];ans=0;}else{int l, r, u;double tmp, len;con[cn] = con[0];ans = 1e40;l = i = 0;while(dmul(con[i], con[i+1], con[i], con[l])>= dmul(con[i], con[i+1], con[i], con[(l-1+cn)%cn])){l = (l-1+cn)%cn;}for(r=u=i = 0; i < cn; i++){while(xmul(con[i], con[i+1], con[i], con[u])<= xmul(con[i], con[i+1], con[i], con[(u+1)%cn])){u = (u+1)%cn;}while(dmul(con[i], con[i+1], con[i], con[r])<= dmul(con[i], con[i+1], con[i], con[(r+1)%cn])){r = (r+1)%cn;}while(dmul(con[i], con[i+1], con[i], con[l])>= dmul(con[i], con[i+1], con[i], con[(l+1)%cn])){l = (l+1)%cn;}tmp = dmul(con[i], con[i+1], con[i], con[r]) - dmul(con[i], con[i+1], con[i], con[l]);tmp *= xmul(con[i], con[i+1], con[i], con[u]);tmp /= dist2(con[i], con[i+1]);len = xmul(con[i], con[i+1], con[i], con[u])/dist(con[i], con[i+1]);if(sign(tmp - ans) < 0){ans = tmp;ds[0] = getRoot(con[l], con[i], con[i+1]);ds[1] = getRoot(con[r], con[i+1], con[i]);ds[2] = change(con[i], con[i+1], ds[1], len);ds[3] = change(con[i], con[i+1], ds[0], len);}}}return ans+eps; }int main () {int t ,n ,i ,NN ,cas = 1;point ds[10];scanf("%d" ,&t);while(t--){scanf("%d" ,&NN);int n = 0;for(i = 1 ;i <= NN ;i ++){for(int j = 1 ;j <= 4 ;j ++){scanf("%lf %lf" ,&ps[n].x ,&ps[n].y);n++;}}double ans = getMinAreaRect(ps ,n ,ds);printf("Case #%d:\n" ,cas ++);printf("%.0lf\n" ,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu5251最小矩形覆盖的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。