```
算法訓(xùn)練 Trash Removal
時(shí)間限制：1.0s 內(nèi)存限制：256.0MB

問題描述
　　Allied Chute公司是一個(gè)建造垃圾管道的公司。垃圾管道建造在樓房中，垃圾從頂部進(jìn)入，順著管道與地下室連接。建造垃圾管道是一個(gè)高水平的工作。根據(jù)人們丟入不同種類的垃圾，垃圾管道需要有一個(gè)適當(dāng)?shù)某叽纭２⑶矣捎谥谱骼艿赖馁M(fèi)用正比于它的尺寸，公司總是想要建造盡可能的管道，盡管確定合適的尺寸十分困難。
　　為了簡化這個(gè)問題，我們考慮一個(gè)二維的空間。垃圾管道是一個(gè)有著固定寬度、垂直下降的槽。物體可以看作一個(gè)多邊形的模型。在物體落入管道之前它可以旋轉(zhuǎn)來達(dá)到和管道最佳擬合。當(dāng)它下落時(shí)，它會垂直落下并且不再旋轉(zhuǎn)。下圖展示了一個(gè)垃圾是怎樣旋轉(zhuǎn)來符合管道的。
　　你的任務(wù)是計(jì)算讓一個(gè)給定的多邊形物體通過的最小管道寬度。
輸入格式
　　輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)開始于一個(gè)數(shù)字n,代表垃圾的模型—一個(gè)多邊形的頂點(diǎn)數(shù)。
　　接下來n行每行一對整數(shù)xi和yi，按順序給出多邊形的頂點(diǎn)。
　　最后以一個(gè)0表示結(jié)束
輸出格式
　　對于每組測試數(shù)據(jù)，輸出數(shù)據(jù)編號以 及物體能夠穿過垃圾管道并落下的最小寬度。輸出的最小寬度并 向上舍入到最接近1/100倍數(shù)的數(shù) ，你的答案與標(biāo)準(zhǔn)答案誤差不能超過1/100。
樣例輸入
3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0
樣例輸出
Case 1: 2.40
Case 2: 14.15
數(shù)據(jù)規(guī)模和約定
　　30%的數(shù)據(jù)3<=n<=15
　　100%的數(shù)據(jù)3<=n<=100
　　0<=xi,yi<=10^4
　　保證在一組數(shù)據(jù)中的所有的點(diǎn)互不不同，并且多邊形的邊不會相交（技術(shù)上，兩條相鄰的邊不可避免的會有一個(gè)公共頂點(diǎn)，當(dāng)然，這種情況我們不認(rèn)為是相交）。
```

```c++
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point {
double x, y;

Point(double a = 0, double b = 0) : x(a), y(b) {}

Point operator - (const Point &b) const {
return Point(x - b.x, y - b.y);
}

bool operator < (const Point &b) const {
return x < b.x || (x == b.x && y < b.y);
}

double norm(){//模的長度
return sqrt(x * x + y * y);
}
};

//計(jì)算a與b(向量積)的值
double cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}

//判斷b在a順時(shí)針還是逆時(shí)針
bool IsClockWise(Point p0, Point p1, Point p2) {
if (cross(p1 - p0, p2 - p1) < 0)
return true;
else
return false;
}

//安德魯算法（Andrew’s Algorithm）求凸包
int Andrew(Point *res, Point *p, int n) {
sort(p, p+n);
int m = 0; //凸包集合計(jì)數(shù)索引
for (int i = 0; i < n; i++) { //從左向右掃描，創(chuàng)建凸包的上部
while (m >= 2 && !IsClockWise(res[m-2], res[m-1], p[i]))
m--;
res[m++] = p[i];
}
int k = m;
for (int i = n - 2; i >= 0; i--) { //從n-2開始是因?yàn)閚-1一定在凸包的上部分，已包含，
while (m > k && !IsClockWise(res[m-2], res[m-1], p[i]))
m--;
res[m++] = p[i];
}
if (m > 0) m--;
return m;
}

//求點(diǎn)到邊的距離
double DistanceToLine(Point p, Point a, Point b) {
double buttom = (a-b).norm();
return fabs(cross(a-p, b-p)) / buttom;
}

int main() {
Point res[105],p[105];
int n;
int cnt = 1;
while (cin >> n && n) {
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
int m = Andrew(res, p, n);
double ans = INFINITY;
//枚舉每一條邊作為低，求高的最小值。i取值從0~m，形成一個(gè)換
for (int i = 0; i <= m; i++) {
double max_high = 0.0;
for (int j = 0; j < m; j++) {
max_high = max(max_high, DistanceToLine(res[j], res[i], res[(i+1)%m]));
}
ans = min(ans,max_high);
}
ans = ceil(ans * 100) / 100;
cout << "Case " << cnt++ << ": " << ans << endl;
}
return 0;
}
```

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhanyeye/p/10246592.html

總結(jié)

以上是生活随笔為你收集整理的ALGO-185 Trash Removal的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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