解題區/解題區 - UVa

UVa 132 - Bumpy Objects

contents

  1. 1. Problem
  2. 2. Input and Output
  3. 3. Sample input
  4. 4. Sample output
  5. 5. Solution

Problem

132img1

Consider objects such as these. They are polygons, specified by the coordinates of a centre of mass and their vertices. In the figure, centres of mass are shown as black squares. The vertices will be numbered consecutively anti-clockwise as shown.

An object can be rotated to stand stably if two vertices can be found that can be joined by a straight line that does not intersect the object, and, when this line is horizontal, the centre of mass lies above the line and strictly between its endpoints. There are typically many stable positions and each is defined by one of these lines known as its base line. A base line, and its associated stable position, is identified by the highest numbered vertex touched by that line.

Write a program that will determine the stable position that has the lowest numbered base line. Thus for the above objects, the desired base lines would be 6 for object 1, 6 for object 2 and 2 for the square. You may assume that the objects are possible, that is they will be represented as non self-intersecting polygons, although they may well be concave.

Input and Output

Successive lines of a data set will contain: a string of less than 20 characters identifying the object; the coordinates of the centre of mass; and the coordinates of successive points terminated by two zeroes (0 0), on one or more lines as necessary. There may be successive data sets (objects). The end of data will be defined by the string ‘#’.

Output will consist of the identification string followed by the number of the relevant base line.

Sample input

1
2
3
4
5
6
7
Object2
4 3
3 2  5 2  6 1  7 1  6 3  4 7  1 1  2 1  0 0
Square 
2 2
1 1  3 1  3 3  1 3  0 0
#

Sample output

1
2
Object2             6
Square              2

Solution

題目描述：

給定一個多邊形，將會給予這個多邊形的質心和頂點。在圖中，質心表示成黑色正方形的小點，而頂點將會使用連續編號逆時針給點。

多邊形可以藉由旋轉放置於水平，並且穩定立起。這時可以發現，會有兩個頂點拉起的水平線，並且質心會位於水平線上的兩個端點之間。

通常一個多邊形具有多個這種水平放置方法，對於一個水平放置方式，可以用在水平線上最大編號的頂點描述。

請輸出最小水平放置的編號。

題目解法：

對多邊形著手凸包計算，這裡使用單調鍊去完成凸包。接著利用內積找到質心是否在兩個水平線端點 (segment 的上方) 之間。

可以利用外積判斷是否在線 (line) 上。

好好利用數學運算，將可以在簡短的代碼完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m - 1;
}
int main() {
    char testcase[105];
    Pt P[1024], CH[1024], IN[1024];
    while(scanf("%s", testcase) == 1) {
        if(!strcmp(testcase, "#"))
            break;
        double 	x, y;
        int 	n = 0, m;
        Pt mc;
        scanf("%lf %lf", &mc.x, &mc.y);
        while(scanf("%lf %lf", &x, &y) == 2) {
            if(x == 0 && y == 0)
                break;
            IN[n] = P[n] = Pt(x, y);
            n++;
        }
        m = monotone(n, P, CH);
        int ret = 0x3f3f3f3f;
        for(int i = 0, j = m - 1; i < m; j = i++) {
            if(between(CH[i], CH[j], mc)) {
                int mn = 0;
                for(int k = 0; k < n; k++)
                    if(onSeg(CH[i], CH[j], IN[k]))
                        mn = max(mn, k);
                ret = min(ret, mn);
            }
        }
        printf("%-20s%d\n", testcase, ret + 1);
    }
    return 0;
}