基础计算几何

POJ 1410 判断线段交和点在凸包内

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cmath>
 4 #define MP make_pair 
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 
 9 const double eps = 1e-8;
10 
11 int sgn(double x) {
12     if (fabs(x) < eps) return 0;
13     return x < 0 ? -1 : 1;
14 }
15 
16 
17 struct Point {
18     double x, y;
19     Point(double x = 0, double y = 0) : x(x), y(y) {}
20     Point operator - (const Point &b) const {
21         return Point(x - b.x, y - b.y);
22     }
23     double operator ^ (const Point &b) const {
24         return x * b.y - y * b.x;
25     }
26     double operator *(const Point &b) const {
27         return x * b.x + y * b.y;
28     }
29 };
30 
31 struct Line {
32     Point s, e;
33     Line(Point s, Point e): s(s), e(e) {}
34 };
35 
36 bool SI(Line l1, Line l2) {
37     return max(l1.s.x, l1.e.x) >= min(l2.s.x, l2.e.x)
38         && max(l2.s.x, l2.e.x) >= min(l1.s.x, l1.e.x)
39         && max(l1.s.y, l1.e.y) >= min(l2.s.y, l2.e.y)
40         && max(l2.s.y, l2.e.y) >= min(l1.s.y, l1.e.y)
41         && sgn((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 
42         && sgn((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn((l1.e - l2.e) ^ (l2.s - l2.e));
43 }
44 
45 bool onSeg(Point P, Line L) {
46     return sgn((L.s - P) ^ (L.e - P)) == 0
47         && sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0
48         && sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
49 }
50 
51 int inConvexPoly(Point a, Point p[], int n) {
52     for (int i = 0; i < n; i++) {
53         if (sgn((p[i] - a) ^ (p[(i + 1) % n] - a)) < 0) return -1;
54         else if (onSeg(a, Line(p[i], p[(i + 1) % n]))) return 0;
55     }
56     return 1;
57 }
58 
59 int main() {
60     int T;
61     double x1, y1, x2, y2;
62     scanf("%d", &T);
63     while (T--) {
64         scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
65         Line line = Line(Point(x1, y1), Point(x2, y2));
66         scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
67         if (x1 > x2) swap(x1, x2);
68         if (y1 > y2) swap(y1, y2);
69         Point p[10];
70         p[0] = Point(x1, y1);
71         p[1] = Point(x2, y1);
72         p[2] = Point(x2, y2);
73         p[3] = Point(x1, y2);
74         if (SI(line, Line(p[0], p[1]))) {puts("T"); continue;}
75         if (SI(line, Line(p[1], p[2]))) {puts("T"); continue;}
76         if (SI(line, Line(p[2], p[3]))) {puts("T"); continue;}
77         if (SI(line, Line(p[3], p[0]))) {puts("T"); continue;}
78         if (inConvexPoly(line.s, p, 4) >= 0 || inConvexPoly(line.e, p, 4) >= 0) {
79             puts("T");
80             continue;
81         }
82         puts("F");
83     }
84 
85     return 0;
86 }

View Code

POJ 2546 求两圆的面积交

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 const double eps = 1e-6;
 9 const double pi = acos(-1.0);
10 
11 struct Circle {
12     double x, y;
13     double r;
14     Circle(double x = 0.0, double y = 0.0, double r = 1.0) : x(x), y(y), r(r) {}
15 };
16 
17 double insectArea(Circle a, Circle b) {
18     double dis = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
19     if (a.r + b.r <= dis) {
20         return 0.0;
21     } else if (fabs(a.r - b.r) >= dis) {
22         return pi * min(a.r, b.r) * min(a.r, b.r);
23     } else {
24         double B1 = acos((a.r * a.r + dis * dis - b.r * b.r) / (2.0 * a.r * dis));
25         double B2 = acos((b.r * b.r + dis * dis - a.r * a.r) / (2.0 * b.r * dis));
26         return B1 * a.r * a.r + B2 * b.r * b.r - dis * a.r * sin(B1);
27     }
28 }
29 
30 int main() {
31     double x, y, r;
32     scanf("%lf%lf%lf", &x, &y, &r);
33     Circle c1 = Circle(x, y, r);
34     scanf("%lf%lf%lf", &x, &y, &r);
35     Circle c2 = Circle(x, y, r);
36     printf("%.3lf
", insectArea(c1, c2));
37     return 0;
38 }

View Code

POJ 2187 对踵点对模板题

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 const double eps = 1e-6;
 9 const int maxn = 5e4 + 10;
10 
11 int n;
12 double x, y;
13 
14 int sgn(double x) {
15     if (fabs(x) < eps) return 0;
16     return x < 0 ? -1 : 1;
17 }
18 
19 struct Point {
20     double x, y;
21     Point(double x = 0, double y = 0): x(x), y(y) {}
22     Point operator - (const Point &b) const {
23         return Point(x - b.x, y - b.y);
24     }
25     double operator ^ (const Point &b) const {
26         return x * b.y - y * b.x;
27     } 
28     double operator * (const Point &b) const {
29         return x * b.x + y * b.y;
30     }
31 };
32 
33 bool cmp(const Point &a, const Point &b) {
34     return sgn(a.x - b.x) == 0 ? (a.y < b.y) : (a.x < b.x);
35 }
36 
37 double dist(Point a, Point b) {
38     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) ;
39 }
40 
41 Point p[maxn], ch[maxn];
42 
43 int ConvexHull() {
44     sort(p, p + n, cmp);
45     int m = 0;
46     for (int i = 0; i < n; i++) {
47         while (m > 1 && sgn((ch[m - 1] - ch[m - 2]) ^ (p[i] - ch[m - 2])) <= 0) m--;
48         ch[m++] = p[i];
49     }
50     int k = m;
51     for (int i = n - 2; i >= 0; i--) {
52         while (m > k && sgn((ch[m - 1] - ch[m - 2]) ^ (p[i] - ch[m - 2])) <= 0) m--;
53         ch[m++] = p[i];
54     }
55     if (n > 1) m--;
56     return m;
57 }
58 
59 void solve() {
60     int m = ConvexHull();
61     if (m == 2) {
62         printf("%.0lf
", dist(ch[0], ch[1]));
63     } else {
64         int i = 0, j = 0;
65         for (int k = 0; k < m; k++) {
66             if (!cmp(ch[i], ch[k])) i = k;
67             if (cmp(ch[j], ch[k])) j = k;
68         }
69         double res = 0.0;
70         int si = i, sj = j;
71         while (si != j || sj != i) {
72             res = max(res, dist(ch[i], ch[j]));
73             double tmp = (ch[(i + 1) % m] - ch[i]) ^ (ch[(j + 1) % m] - ch[j]);
74             if (sgn(tmp) < 0) {
75                 i = (i + 1) % m;
76             } else {
77                 j = (j + 1) % m;
78             }
79         }
80         printf("%.0lf
", res);
81     }
82     
83 }
84 
85 int main() {
86     scanf("%d", &n);
87     for (int i = 0; i < n; i++) {
88         scanf("%lf%lf", &x, &y);
89         p[i].x = x; p[i].y = y;
90     }
91     solve();
92 
93     return 0;
94 }

View Code

POJ 1584 判断凸多边形，点在多边形内；计算点到线段距离(但事实上思考一下就会发现直接求点到直线距离即可)

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cmath>
  4 using namespace std;
  5 
  6 typedef long long LL;
  7 
  8 const double eps = 1e-8;
  9 const double pi = acos(-1.0);
 10 
 11 int sgn(double x) {
 12     if (fabs(x) < eps) return 0;
 13     return x < 0 ? -1 : 1;
 14 }
 15 
 16 struct Point {
 17     double x, y;
 18     Point(double x = 0.0, double y = 0.0): x(x), y(y) {}
 19     Point operator - (const Point &b) const {
 20         return Point(x - b.x, y - b.y);
 21     }
 22     double operator ^ (const Point &b) const {
 23         return x * b.y - y * b.x;
 24     }
 25     double operator * (const Point &b) const {
 26         return x * b.x + y * b.y;
 27     }
 28 };
 29 
 30 struct Line {
 31     Point s, e;
 32     Line() {}
 33     Line(Point s, Point e) : s(s), e(e) {}
 34 };
 35 
 36 double dist(Point a, Point b) {
 37     double t = (a - b) * (a - b);
 38     return sqrt(t);
 39 }
 40 
 41 bool isCH(Point poly[], int n) {
 42     bool s[3];
 43     s[0] = s[1] = s[2] = false;
 44     for (int i = 0; i < n; i++) {
 45         s[sgn((poly[(i + 1) % n] - poly[i]) ^ (poly[(i + 2) % n] - poly[i])) + 1] = true;
 46         if (s[0] && s[2]) return false;
 47     }
 48     return true;
 49 }
 50 
 51 Point PTS(Point P, Line L) {
 52     Point result;
 53     Point v = L.e - L.s;
 54     double t = (P - L.s) * v / (v * v);
 55 //    if (t >= 0 && t <= 1) {
 56         result.x = L.s.x + t * v.x;
 57         result.y = L.s.y + t * v.y;
 58 //    } else {
 59 //        if (dist(P, L.s) < dist(P, L.e)) result = L.s;
 60 //        else result = L.e;
 61 //    }
 62     return result;
 63 }
 64 
 65 bool onSeg(Point P, Line L) {
 66     return sgn((L.s - P) ^ (L.e - P)) == 0
 67         && sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0
 68         && sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
 69 }
 70 
 71 int inCP(Point a, Point p[], int n) {
 72     for (int i = 0; i < n; i++) {
 73         if (sgn((p[i] - a) ^ (p[(i + 1) % n] - a)) < 0) return -1;
 74         else if (onSeg(a, Line(p[i], p[(i + 1) % n]))) return 0;
 75     }
 76     return 1;
 77 }
 78 
 79 bool inter(Line l1, Line l2) {
 80     return max(l1.s.x, l1.e.x) >= min(l2.s.x, l2.e.x) 
 81         && max(l2.s.x, l2.e.x) >= min(l1.s.x, l1.e.x)
 82         && max(l1.s.y, l1.e.y) >= min(l2.s.y, l2.e.y)
 83         && max(l2.s.y, l2.e.y) >= min(l1.s.y, l1.e.y)
 84         && sgn((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0
 85         && sgn((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;
 86 }
 87 
 88 int inPoly(Point P, Point poly[], int n) {
 89     int cnt = 0;
 90     Line ray, side;
 91     ray.s = P;
 92     ray.e.y = P.y;
 93     ray.e.x = -100000000000.0;
 94 
 95     for (int i = 0; i < n; i++) {
 96         side.s = poly[i];
 97         side.e = poly[(i + 1) % n];
 98 
 99         if (onSeg(P,side)) return 0;
100         if (sgn(side.s.y - side.e.y) == 0) continue;
101         if(onSeg(side.s,ray)) {
102             if(sgn(side.s.y - side.e.y) > 0) cnt++;
103         } else if(onSeg(side.e,ray)) {
104             if(sgn(side.e.y - side.s.y) > 0)cnt++;
105         } else if(inter(ray,side)) {
106             cnt++;
107         }
108     }
109     if (cnt % 2 == 1) return 1;
110     else return -1;
111 }
112 
113 
114 Point p[110];
115 int main() {
116     int n;
117     double R,x,y;
118     while (scanf("%d",&n) == 1) {
119         if (n < 3) break;
120         scanf("%lf%lf%lf", &R, &x, &y);
121         for (int i = 0; i < n; i++) {
122             scanf("%lf%lf", &p[i].x, &p[i].y);
123         }
124         if (!isCH(p, n)) {
125             puts("HOLE IS ILL-FORMED");
126             continue;
127         }
128         Point P = Point(x, y);
129         bool flag = true;
130         if (inPoly(P, p, n) >= 0) {
131             for (int i = 0; i < n && flag; i++) {
132                 if (sgn(dist(P, PTS(P, Line(p[i], p[(i + 1) % n]))) - R) < 0) {
133                     flag = false;
134                 }
135             }
136         } else {
137             flag = false;
138         }
139         if (flag) {
140             puts("PEG WILL FIT");
141         } else {
142             puts("PEG WILL NOT FIT");
143         }
144     }
145     return 0;
146 }

View Code

POJ 1873 枚举加凸包模板

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cmath>
  5 using namespace std;
  6 typedef long long LL;
  7 
  8 const double eps = 1e-8;
  9 
 10 int sgn(double x) {
 11     if (fabs(x) < eps) return 0;
 12     return x < 0 ? -1 : 1;
 13 }
 14 
 15 struct Point {
 16     double x, y, l;
 17     int v;
 18     Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}
 19     Point operator - (const Point &b) const {
 20         return Point(x - b.x, y - b.y);
 21     }
 22     double operator ^ (const Point &b) const {
 23         return x * b.y - y * b.x;
 24     }
 25     double operator * (const Point &b) const {
 26         return x * b.x + y * b.y;
 27     }
 28 };
 29 
 30 bool cmp(const Point &a, const Point &b) {
 31     return sgn(a.x - b.x) == 0 ? (a.y < b.y) : (a.x < b.x);
 32 }
 33 
 34 double dist(Point a, Point b) {
 35     Point c = a - b;
 36     return sqrt(c * c);
 37 }
 38 
 39 Point p[20], ch[20];
 40 Point pp[20];
 41 
 42 
 43 int ConvexHull(int m) {
 44     sort(pp, pp + m, cmp);
 45     int num = 0;
 46     for (int i = 0; i < m; i++) {
 47         while (num > 1 && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--;
 48         ch[num++] = pp[i];
 49     }
 50     int k = num;
 51     for (int i = m - 2; i >= 0; i--) {
 52         while (num > k && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--;
 53         ch[num++] = pp[i];
 54     }
 55     if (m > 1) num--;
 56     return num;
 57 }
 58 
 59 int n;
 60 int cnt;
 61 double ans_l;
 62 int ans_v, ans_c;
 63 
 64 int ans;
 65 
 66 
 67 void init() {
 68     ans = 0;
 69     ans_v = 200000.0;
 70     ans_l = 0.0;
 71     ans_c = 20;
 72 }
 73 
 74 void solve() {
 75     for (int bit = (1 << n) - 1; bit ; bit--) {
 76         int cnt = 0;
 77         double l = 0.0;
 78         double c = 0.0;
 79         int v = 0;
 80         for (int i = 0; i < n; i++) {
 81             if (bit & (1 << i)) {
 82                 l += p[i].l;
 83                 v += p[i].v;
 84             } else {
 85                 pp[cnt++] = p[i];
 86             }
 87         }
 88         cnt = ConvexHull(cnt);
 89 
 90         for (int i = 0; i < cnt; i++) {
 91             c += dist(ch[i], ch[(i + 1) % cnt]);
 92         }
 93         bool flag = false;
 94         if (sgn(l - c) >= 0) {
 95             if (v < ans_v) {
 96                 flag = true;
 97             } else if (v == ans_v) {
 98                 if (cnt <= ans_c) flag = true;
 99             }
100         }
101         if (flag) {
102             ans_v = v; ans_c = cnt;
103             ans = bit;
104             ans_l = l - c;
105         }
106     }
107 }
108 
109 int main() {
110     double x, y, l;
111     int v;
112     int te = 0;
113     while (scanf("%d", &n), n) {
114         init();
115         for (int i = 0; i < n; i++) {
116             scanf("%lf%lf%d%lf", &p[i].x, &p[i].y, &p[i].v, &p[i].l);
117         }
118         solve();
119         printf("Forest %d
", ++te);
120         printf("Cut these trees:");
121         for (int i = 0; i < 15; i++) {
122             if (ans & (1 << i)) {
123                 printf(" %d", i + 1);
124             }
125         }puts("");
126         printf("Extra wood: %.2lf

", ans_l);
127     }
128     return 0;
129 }

View Code

HDU 3007 最小圆覆盖模板题

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 const double eps = 1e-6;
 8 
 9 int sgn(double x) {
10     if (fabs(x) < eps) return 0;
11     return x < 0 ? -1 : 1;
12 }
13 
14 struct Point {
15     double x, y;
16     Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}
17     Point operator - (const Point &b) const {
18         return Point(x - b.x, y - b.y);
19     }    
20     Point operator + (const Point &b) const {
21         return Point(x + b.x, y + b.y);
22     }
23     double operator ^ (const Point &b) const {
24         return x * b.y - y * b.x;
25     }
26     double operator * (const Point &b) const {
27         return x * b.x + y * b.y;
28     }
29     Point operator / (double times) const {
30         return Point(x / times, y / times);
31     }
32     Point operator * (double times) const {
33         return Point(x * times, y * times);
34     }
35 };
36 
37 Point center;
38 
39 Point outer(Point a, Point b, Point c) {
40     double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
41     double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
42     double d = a1 * b2 - a2 * b1;
43     return Point(a.x - (c2 * b1 - c1 * b2) / d, a.y + (a1 * c2 - a2 * c1) / d);
44 }
45 
46 double dis(Point a, Point b) {
47     return sqrt((a - b) * (a - b));
48 }
49 
50 int n;
51 
52 Point p[510];
53 double r;
54 
55 void solve() {
56     r = 0;
57     center = p[0];
58     for (int i = 1; i < n; i++) {
59         if (sgn(dis(center, p[i]) - r) > 0) {
60             center = p[i]; r = 0;
61             for (int j = 0; j < i; j++) {
62                 if (sgn(dis(center, p[j]) - r) > 0) {
63                     center = (p[i] + p[j]) / 2;
64                     r = dis(p[i], center);
65                     for (int k = 0; k < j; k++) {
66                         if (sgn(dis(center, p[k]) - r) > 0) {
67                             center = outer(p[i], p[j], p[k]);
68                             r = dis(center, p[k]);
69                         }
70                     }
71                 }
72             }
73         }
74     }
75     printf("%.2lf %.2lf %.2lf
", center.x, center.y, r);
76 }
77 
78 int main() {
79     while (scanf("%d", &n), n) {
80         for (int i = 0; i < n; i++) {
81             scanf("%lf%lf", &p[i].x, &p[i].y);
82         }
83         solve();
84     }
85     return 0;
86 }

View Code

POJ 3568 求两个凸包间

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <algorithm>
  4 using namespace std;
  5 typedef long long LL;
  6 
  7 const double eps = 1e-6;
  8 const int maxn = 1e4 + 10;
  9 const double INF = 1e20;
 10 
 11 int sgn(double x) {
 12     if (fabs(x) < eps) return 0;
 13     return x < 0 ? -1 : 1;
 14 }
 15 
 16 struct Point {
 17     double x, y;
 18     Point(double x = 0, double y = 0): x(x), y(y) {}
 19     Point operator - (const Point &b) const {
 20         return Point(x - b.x, y - b.y);
 21     }
 22     double operator * (const Point &b) const {
 23         return x * b.x + y * b.y;
 24     }
 25     double operator ^ (const Point &b) const {
 26         return x * b.y - y * b.x;
 27     }
 28 };
 29 
 30 bool cmp(const Point &a, const Point &b) {
 31     return sgn(a.x - b.x) == 0 ? (a.y < b.y) : (a.x < b.x);
 32 }
 33 
 34 double dist(Point a, Point b) {
 35     double t = (a - b) * (a - b);
 36     return sqrt(t);
 37 }
 38 
 39 struct Line {
 40     Point s, e;
 41     Line(Point s, Point e): s(s), e(e) {}
 42 };
 43 
 44 Point PST(Point P, Line l) {
 45     Point result;
 46     Point v = l.e - l.s;
 47     double t = (P - l.s) * v / (v * v);
 48     if (0 <= t && t <= 1) {
 49         result.x = l.s.x + t * v.x;
 50         result.y = l.s.y + t * v.y;
 51     } else {
 52         if (dist(P, l.s) < dist(P, l.e)) result = l.s;
 53         else result = l.e;
 54     }
 55     return result;
 56 }
 57 
 58 double _PTS(Point p0, Point p1, Point p2) {
 59     return dist(p0, PST(p0, Line(p1, p2)));
 60 }
 61 
 62 double STS(Point p0, Point p1, Point p2, Point p3) {
 63     double ans1 = min(_PTS(p0, p2, p3), _PTS(p1, p2, p3));
 64     double ans2 = min(_PTS(p2, p0, p1), _PTS(p3, p0, p1));
 65     return min(ans1, ans2);
 66 }
 67 
 68 
 69 int ConvexHull(Point pp[], int m, Point ch[]) {
 70     sort(pp, pp + m, cmp);
 71     int num = 0;
 72     for (int i = 0; i < m; i++) {
 73         while (num > 1 && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--;
 74         ch[num++] = pp[i];
 75     }
 76     int k = num;
 77     for (int i = m - 2; i >= 0; i--) {
 78         while (num > k && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--;
 79         ch[num++] = pp[i];
 80     }
 81     if (m > 1) num--;
 82     return num;
 83 }
 84 
 85 
 86 double getAngle(Point a1, Point a2, Point b1, Point b2) {
 87     return (a2 - a1) ^ (b1 - b2);
 88 }
 89 
 90 double rotating(Point *p, int np, Point *q, int nq) {
 91     int sp = 0, sq = 0;
 92     for (int i = 0; i < np; i++) {
 93         if (sgn(p[i].y - p[sp].y) < 0) sp = i;
 94     }
 95     for (int i = 0; i < nq; i++) {
 96         if (sgn(q[i].y - q[sq].y) > 0) sq = i;
 97     }
 98     double tmp;
 99     double ans = INF;
100 
101     for (int i = 0; i < np; i++) {
102         while (sgn(tmp = getAngle(p[sp], p[(sp + 1) % np], q[sq], q[(sq + 1) % nq])) < 0) {
103             sq = (sq + 1) % nq;
104         }
105         if (sgn(tmp) == 0) {
106             ans = min(ans, STS(p[sp], p[(sp + 1) % np], q[sq], q[(sq + 1) % nq]));
107         } else {
108             ans = min(ans, _PTS(q[sq], p[sp], p[(sp + 1) % np]));
109         }
110         sp = (sp + 1) % np;
111     }
112     return ans;
113 }
114 
115 
116 Point p1[maxn], p2[maxn];
117 Point ch1[maxn], ch2[maxn];
118 
119 
120 double solve(Point *p, int n, Point *q, int m) {
121     n = ConvexHull(p1, n, ch1);
122     m = ConvexHull(p2, m, ch2);
123     return min(rotating(ch1, n, ch2, m), rotating(ch2, m, ch1, n));
124 }
125 
126 int main() {
127     int n, m;
128     while (scanf("%d%d", &n, &m), n && m) {
129         for (int i = 0; i < n; i++) {
130             scanf("%lf%lf", &p1[i].x, &p1[i].y);
131         }
132         for (int i = 0; i < m; i++) {
133             scanf("%lf%lf", &p2[i].x, &p2[i].y);
134         }
135         double ans = solve(p1, n, p2, m);
136         printf("%.5lf
", ans);
137     }
138     return 0;
139 }

View Code

POJ 1696 极角排序

POJ 1228 稳定凸包

POJ 3525 半平面交求凸多边形内部点到边界最大距离

uva 4642 给出三角形三个顶点，求出三个圆的半径，三个圆满足两两相切且都与三角形相切

POJ 1981 问一个单位圆最多能覆盖多少个给出的点(n<=300)

HDU 6097 圆的反演基础题

uva 4676 给定两个三角形速度和顶点，求相撞时刻