poj1113-Wall
Wall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 31394 Accepted: 10610
Description
Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's castle. The King was so greedy, that he would not listen to his Architect's proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall.
Input
The first line of the input file contains two integer numbers N and L separated by a space. N (3 <= N <= 1000) is the number of vertices in the King's castle, and L (1 <= L <= 1000) is the minimal number of feet that King allows for the wall to come close to the castle.Output
Write to the output file the single number that represents the minimal possible length of the wall in feet that could be built around the castle to satisfy King's requirements. You must present the integer number of feet to the King, because the floating numbers are not invented yet. However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches), since the King will not tolerate larger error in the estimates.Sample Input
9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200
Sample Output
1628
Hint
結果四捨五入就可以了Source
Northeastern Europe 2001
題意:給定N個點,求最小的圖形,使得所有點均在凸多邊形內,且任一點到凸多邊形的距離不小於L,求圖形最小的周長.
首先想到凸包.
但是有距離不小於L的限制,那麼考慮以每個點作一個半徑為L的圓.
那麼最終圖形一定包含所有的N個圓.
最終圖形包括直線和弧.
直線便與圓相切,切對應直線的∑長度=凸包周長,
接下來考慮∑弧長,每一段弧都對應一個轉折點.
考慮圓上的一點i,經過每一段弧後回到原來的位置.
即∑弧長=以L為半徑的圓的周長.
那麼最終答案 = 凸包周長 + 2×π×R.
code:
#include#include #include #include #include #include using namespace std; #define rep(i, l, r) for (int i = l; i <= r; i++) #define REP(i, l, r) for (int i = l; i >= r; i--) #define PI (3.14159265358979323846264) #define INF 19971228 #define MAXN 1010 int n, L, stack[MAXN], top; struct point {int x, y;} a[MAXN], p0; point operator -(point a, point b) {a.x = a.x - b.x, a.y = a.y - b.y; return a;} int operator ^(point a, point b) {return a.x*b.y - a.y*b.x;} int operator *(point a, point b) {a = a - p0, b = b - p0; return a^b;} inline int sqr(int x) {return x*x;} inline double dist(point a, point b) {return sqrt(sqr(a.y-b.y) + sqr(a.x-b.x));} inline bool cmp(point a, point b) { if (a*b > 0) return 1; else if (a*b == 0 && dist(a, p0) < dist(b, p0)) return 1; return 0; } inline bool left(point a, point b, point c) { point v1, v2; v1.x = b.x - a.x, v1.y = b.y - a.y; v2.x = c.x - b.x, v2.y = c.y - b.y; return (v1^v2) > 0; } inline void graham() { a[++n] = a[1]; top = 0; stack[++top] = 1; stack[++top] = 2; stack[++top] = 3; rep(i, 4, n) { while (!left(a[stack[top-1]], a[stack[top]], a[i])) top--; stack[++top] = i; } } int main() { cin >> n >> L; int minx = INF, miny = INF, k; rep(i, 1, n) { scanf("%d%d", &a[i].x, &a[i].y); if (a[i].x < minx || (a[i].x == minx && a[i].y < miny)) minx = a[i].x, miny = a[i].y, k = i; } p0.x = minx, p0.y = miny; sort(a+1, a+1+n, cmp); graham(); double ans = 0; rep(i, 2, top) ans += dist(a[stack[i-1]], a[stack[i]]); ans += 2 * PI * L; printf("%d\n", int(ans + 0.5)); return 0; }
