UVALive4974 CERC2010B Beasts
24844 단어 live
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #include<algorithm>
5 #include<iostream>
6 #include<math.h>
7 using namespace std;
8 const int maxn = 211111;
9 const double eps = 1e-9;
10 typedef double PELEM;
11 typedef long long LL;
12 struct Point
13 {
14 PELEM x, y;
15 Point()
16 {
17 x = y = 0;
18 }
19 Point(PELEM a, PELEM b)
20 {
21 x = a, y = b;
22 }
23 PELEM cross(const Point &b, const Point &c)const
24 {
25 return (b.x - x) * (c.y - y)
26 - (c.x - x) * (b.y - y);
27 }
28 PELEM dot(const Point &p)const
29 {
30 return x * p.x + y * p.y;
31 }
32 Point operator-(const Point &p)const
33 {
34 return Point(x - p.x, y - p.y);
35 }
36 Point operator+(const Point &p)const
37 {
38 return Point(x + p.x, y + p.y);
39 }
40 Point operator-()const
41 {
42 return Point(-x, -y);
43 }
44 } p[2][maxn << 1];
45 struct Line
46 {
47 LL a, b, c;
48 bool operator<(const Line &l)const
49 {
50 if(a *l.b == b * l.a)
51 return l.c * b < c * l.b;
52 return a * l.b > b * l.a;
53 }
54 int CmXL(const Line &l)const
55 {
56 if(a * l.b < b * l.a) return 1;
57 else if(a * l.b > b * l.a) return -1;
58 return 0;
59 }
60 bool paral(const Line &l)const
61 {
62 return a * l.b == b * l.a;
63 }
64 bool high(const Point &p)const
65 {
66 return p.x * a + p.y * b - c > eps;
67 }
68 Point CrossP(const Line &l)const
69 {
70 return Point((double)(c * l.b - l.c * b) / (a * l.b - l.a * b),
71 (double)(c * l.a - l.c * a) / (b * l.a - l.b * a));
72 }
73 };
74 void HPC(Line l[], int n, Point p[], Line nl[], int &pm, int &lm)
75 {
76 int i, tn;
77 sort(l, l + n);
78 pm = lm = 0;
79 nl[lm ++] = l[0];
80 for(i = 1; i < n; ++ i)
81 {
82 if(lm && nl[lm - 1].paral(l[i])) continue;
83 while(pm && !l[i].high(p[pm - 1]))
84 -- pm, -- lm;
85 p[pm ++] = nl[lm - 1].CrossP(l[i]);
86 nl[lm ++] = l[i];
87 }
88 if(pm == 0) p[pm ++] = Point(0, (double)nl[0].c / nl[0].b);
89 }
90 int n, pn1, pn2, ln1, ln2;
91 Line l[maxn], l1[maxn], l2[maxn];
92 Point p1[maxn], p2[maxn];
93 Point CrossPoint(Point a, Point b, Point c, Point d)
94 {
95 double u = a.cross(b, c), v = b.cross(a, d);
96 return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
97 }
98 double DisPtoP(Point a, Point b)
99 {
100 return (a - b).dot(a - b);
101 }
102
103 double DisPtoS(Point p, Point a, Point b, bool mk)
104 {
105 Point t = Point(p.x + a.y - b.y, p.y + b.x - a.x);
106 if(mk && (t - a).dot(b - a) > eps || t.cross(a, p) * t.cross(b, p) < -eps)
107 return DisPtoP(p, CrossPoint(t, p, a, b));
108 return min(DisPtoP(p, a), DisPtoP(p, b));
109 }
110 double DisStoS(Point a, Point b, Point c, Point d)
111 {
112 double ans = 1e30;
113 ans = min(ans, DisPtoS(a, c, d, 0));
114 ans = min(ans, DisPtoS(b, c, d, 0));
115 ans = min(ans, DisPtoS(c, a, b, 0));
116 ans = min(ans, DisPtoS(d, a, b, 0));
117 return ans;
118 }
119 int main()
120 {
121 int t, i, j, k;
122 double ans;
123 Point ts, te;
124 for(scanf("%d", &t); t --; )
125 {
126 ans = 1e30;
127 scanf("%d", &n);
128 for(i = 0; i < n; ++ i)
129 {
130 scanf("%lld%lld%lld", &l[i].a, &l[i].b, &l[i].c), l[i].c = -l[i].c;
131 if(l[i].b < 0) l[i].a = -l[i].a, l[i].b = -l[i].b, l[i].c = -l[i].c;
132 }
133 HPC(l, n, p1, l1, pn1, ln1);
134 for(i = 0; i < n; ++ i)
135 l[i].a = -l[i].a, l[i].c = -l[i].c;
136 HPC(l, n, p2, l2, pn2, ln2);
137 for(i = 0; i < ln2; ++ i)
138 l2[i].a = -l2[i].a, l2[i].c = -l2[i].c;
139 for(i = 0; i < pn2; ++ i)
140 p2[i].y = -p2[i].y;
141 for(i = 0, j = pn2 - 1; i + 1 < pn1 || j;)
142 {
143 if(j && (i == pn1 - 1 || l1[i + 1].CmXL(l2[j]) == 1))
144 ans = min(ans, DisPtoS(p1[i], p2[j - 1], p2[j], 0)), -- j;
145 else if(i < pn1 - 1 && (!j || l1[i + 1].CmXL(l2[j]) == -1))
146 ans = min(ans, DisPtoS(p2[j], p1[i], p1[i + 1], 0)), ++ i;
147 else
148 {
149 ans = min(ans, DisStoS(p1[i], p1[i + 1], p2[j - 1], p2[j]));
150 ++ i, -- j;
151 }
152 }
153 ts = Point(p2[0].x - 1, (l2[0].c - l2[0].a * (p2[0].x - 1)) / l2[0].b);
154 te = Point(p2[pn2 - 1].x + 1, (l2[pn2].c - l2[pn2].a * (p2[pn2 - 1].x + 1)) / l2[pn2].b);
155 for(i = 0; i < pn1; ++ i)
156 {
157 ans = min(ans, DisPtoS(p1[i], p2[0], ts, 1));
158 ans = min(ans, DisPtoS(p1[i], p2[pn2 - 1], te, 1));
159 }
160 ts = Point(p1[0].x - 1, (l1[0].c - l1[0].a * (p1[0].x - 1)) / l1[0].b);
161 te = Point(p1[pn1 - 1].x + 1, (l1[pn1].c - l1[pn1].a * (p1[pn1 - 1].x + 1)) / l1[pn1].b);
162 for(i = 0; i < pn2; ++ i)
163 {
164 ans = min(ans, DisPtoS(p2[i], p1[0], ts, 1));
165 ans = min(ans, DisPtoS(p2[i], p1[pn1 - 1], te, 1));
166 }
167 printf("%.6f
", ans);
168 }
169 return 0;
170 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vvalive 6323 상태 압축 DP텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.