解題區/解題區 - UVa

UVa 11243 - Texas Trip

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

After a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes in the door of his SUV. The local American Tire store sells fiberglass patching material only in square sheets. What is the smallest patch that Harry needs to fix his door?

Assume that the holes are points on the integer lattice in the plane. Your job is to find the area of the smallest square that will cover all the holes.

Input

The first line of input contains a single integer T expressed in decimal with no leading zeroes, denoting the number of test cases to follow. The subsequent lines of input describe the test cases.

Each test case begins with a single line, containing a single integer n expressed in decimal with no leading zeroes, the number of points to follow; each of the following n lines contains two integers x and y, both expressed in decimal with no leading zeroes, giving the coordinates of one of your points.

You are guaranteed that T <= 30 and that no data set contains more than 30 points. All points in each data set will be no more than 500 units away from (0,0).

Output

Print, on a single line with two decimal places of precision, the area of the smallest square containing all of your points. An answer will be accepted if it lies within 0.1 of the correct answer.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
4
-1 -1
1 -1
1 1
-1 1
4
10 1
10 -1
-10 1
-10 -1

Sample Output

1
2
4.00
242.00

Solution

題目描述：

給平面上 N 個點，找到最小面積的正方形覆蓋所有點。

題目解法：

做一次凸包，得到逆時針的點順序，對於每一個凸包頂點進行，使用三分搜索找到相對應的寬。

進行三分搜索的線段為如下圖所示

p11243.png

對於通過 B 點的所有線段，考慮與下一個凸包頂點所夾的角度( < 180 度)，如圖範例所示即三分再 45 度的區域之中。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
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;
}
double distProjection(Pt as, Pt at, Pt s) {
    double a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
struct Seg {
    Pt s, e;
};
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
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;
}
#define INF 1e+30 
// ternary search
double calcSquare(double m, Pt p, Pt ch[], int n) {
    double a, b, c, lab;
    double w = 0, hl = 0, hr = 0, h;
    a = sin(m), b = -cos(m), c = - (a * p.x + b * p.y), lab = hypot(a, b);
    
    int pp = 0, qq = 0;
    for(int i = 0; i < n; i++) {
        double d = fabs(a * ch[i].x + b * ch[i].y + c) / lab;
        w = max(w, d);
        if(a * ch[i].x + b * ch[i].y + c < - 1e-6)
            pp++;
        if(a * ch[i].x + b * ch[i].y + c > 1e-6)
            qq++;
    }
//	printf("%d %d\n", pp, qq);
    a = cos(m), b = sin(m), c = - (a * p.x + b * p.y), lab = hypot(a, b);
    for(int i = 0; i < n; i++) {
        double d = fabs(a * ch[i].x + b * ch[i].y + c) / lab;
        if(a * ch[i].x + b * ch[i].y + c < 0)
            hl = max(hl, d);
        else
            hr = max(hr, d);
    }
    h = hl + hr;
    return max(w, h) * max(w, h);
}
const double pi = acos(-1);
double ternary_search(double l, double r, Pt p, Pt ch[], int n) {
    double mid, midmid, md, mmd;
    double ret = INF;
    while(fabs(l-r) > eps) {
        mid = (l+r)/2;
        midmid = (mid+r)/2;
        md = calcSquare(mid, p, ch, n);
        mmd = calcSquare(midmid, p, ch, n);
        ret = min(ret, md);
        ret = min(ret, mmd);
        if(md < mmd)
            r = midmid;
        else
            l = mid;
    }
//	printf("best %lf %lf\n", l / pi * 180, ret);
    return ret;
}
double smallSquare(int n, Pt ch[]) {
    double ret = INF;
    
    for(int i = 0, j = n-1; i < n; j = i++) {
//		printf("pt[%lf %lf]\n", ch[i].x, ch[i].y);
        double l = atan2(ch[j].y - ch[i].y, ch[j].x - ch[i].x);
        double r = atan2(ch[(i+1)].y - ch[i].y, ch[(i+1)].x - ch[i].x) - pi;
//		printf("l r [%lf %lf]\n", l, r);
        r = l + fmod(fmod(r - l, 2 * pi) + 2 * pi, 2 * pi);
        if(l <= r) {
            ret = min(ret, ternary_search(l, r, ch[i], ch, n));
        } else {
            ret = min(ret, ternary_search(l, pi, ch[i], ch, n));
            ret = min(ret, ternary_search(-pi, r, ch[i], ch, n));
        }
    }
    return ret;
}
int main() {
    Pt p[2048], ch[2048];
    int n, m;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d", &n);
    	for(int i = 0; i < n; i++)
    		scanf("%lf %lf", &p[i].x, &p[i].y);
        m = monotone(n, p, ch);
//        for(int i = 0; i < m; i++)
//        	printf("%lf %lf\n", ch[i].x, ch[i].y);
    	
    	if(m == 1) {
    		printf("%.2lf\n", 0);
    		continue;
    	}
        double ret = smallSquare(m, ch);
        printf("%.2lf\n", ret);
    }
    return 0;
}