小凸想跑步-半平面交 | Kyons'Blog 




 
 
 
 



 
 



小凸想跑步-半平面交

题目大意

在一个凸包里,找一个点$p$,使得该点与$\{k,k+1,k\in(1,n-1)\}$组成的三角形面积大于和$\{0,1\}$组成的三角形面积.

解析

首先,我们考虑点的取值范围.
必定在凸包内以及凸包的边界上.
线性规划半平面交表示即为:每个边所在直线的左半边区域交集.
再考虑,三角形面积关系:
$\overrightarrow{(x_1-x,y_1-y)}\times\overrightarrow{(x_0-x,y_0-y)}\leq\overrightarrow{(x_{k+1}-x,y_{k+1}-y)}\times\overrightarrow{(x_k-x,y_k-y)}$
然后一堆化简整理之后:
$(y_1-y_0-y_{k+1}+y_k)x+(x_0-x_1-x_k+x_{k+1})y+(x_1y_0-x_0y_1-x_{k+1}y_k+x_ky_{k+1})\ge 0$
一个形如$ax+by+c\ge 0$的式子就写出来了.
对于一个形如上述的式子,该直线的向量为$(b,-a)$,根据这个就可以用两点式表示直线.
然后对于$k\in\{1,n-1\}$的点,都求一次直线.
再与上面的直线求半平面交.得到符合条件的解即可.

代码戳我戳我
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
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;
const double pi = acos(-1.0);
const double inf = 1e100;
const double eps = 1e-12;

typedef struct point vec; //向量vec
struct point { //点的基本数据结构
double x, y;
double poe;
point(double _x = 0, double _y = 0)
: x(_x)
, y(_y)
{
}
point operator*(const point& i_T) const
{
return point(x * i_T.x, y * i_T.y);
}
point operator*(double u) const
{
return point(x * u, y * u);
}
bool operator==(const point& i_T) const
{
return x == i_T.x && y == i_T.y;
}
point operator/(double u) const
{
return point(x / u, y / u);
}
point operator+(const point& i_T)
{
return point(x + i_T.x, y + i_T.y);
}
point operator-(const point& i_T)
{
return point(x - i_T.x, y - i_T.y);
}
friend bool operator<(point a, point b)
{
return a.y == b.y ? a.x < b.x : a.y < b.y;
}
void atn2()
{
poe = atan2(y, x);
}
friend ostream& operator<<(ostream& out, point& a)
{
//cout << a.x << ' ' << a.y;
printf("%.2f %.2f", a.x, a.y);
return out;
}
friend istream& operator>>(istream& in, point& a)
{
scanf("%lf%lf", &a.x, &a.y);
return in;
}
};
typedef struct Line Segment; //线段Segment
struct Line { //直线
point a, b;
double poe;
Line(point _a = point(), point _b = point())
: a(_a)
, b(_b)
{
}
bool operator==(const Line& i_T) const
{
return a == i_T.a && b == i_T.b;
}
friend istream& operator>>(istream& in, Line& a)
{
cin >> a.a >> a.b;
return in;
}
friend ostream& operator<<(ostream& out, Line& a)
{
out << a.a << ' ' << a.b;
return out;
}
void atn2()
{
poe = atan2(b.y - a.y, b.x - a.x);
}
};
double chaji(vec A, vec B) //求向量叉积
{
return A.x * B.y - A.y * B.x; // 正为A->B左旋
}
int zhengfu(double d) //判断正负
{
if (fabs(d) < eps)
return 0;
if (d > 0)
return 1;
return -1;
}
int bijiao(double x, double y)
{
if (fabs(x - y) < eps)
return 0;
if (x > y)
return 1;
return -1;
}
bool cmp(Line l1, Line l2) //半平面交的极角排序
{
return bijiao(l1.poe, l2.poe) == 0 ? zhengfu(chaji(l1.b - l1.a, l2.b - l1.a)) > 0 : l1.poe < l2.poe;
}
point p[MAXN];
Line l[MAXN], q[MAXN];
point zhixian_zhixian_jiaodian(Line l1, Line l2) //两直线交点
{
double t = ((l1.a.x - l2.a.x) * (l2.a.y - l2.b.y) - (l1.a.y - l2.a.y) * (l2.a.x - l2.b.x)) / ((l1.a.x - l1.b.x) * (l2.a.y - l2.b.y) - (l1.a.y - l1.b.y) * (l2.a.x - l2.b.x));
return l1.a + (l1.b - l1.a) * t;
}

double duobianxingmianji(point po[], int num) //多边形面积
{
double ans = 0;
po[num + 1] = po[1];
for (int i = 1; i <= num; i++)
ans += chaji(po[i], po[i + 1]);
ans = fabs(ans) * 0.5;
return ans;
}
double solve(int head, int tail)
{
int num = 0;
q[tail + 1] = q[head];
for (int i = head; i <= tail; i++)
p[++num] = zhixian_zhixian_jiaodian(q[i], q[i + 1]);
if (num < 3)
return 0;
return duobianxingmianji(p, num);
}
bool check(Line a, Line b, Line c) //判断a,b交点是否在c的右边
{
point o = zhixian_zhixian_jiaodian(a, b);
return zhengfu(chaji(c.b - c.a, o - c.a)) < 0;
}

void banpingmian_jiao(int& head, int& tail, Line L[], int t) //求半平面交
{
sort(L + 1, L + t + 1, cmp);
head = 1, tail = 0;
int cnt = 0;
for (int i = 1; i < t; i++) {
if (bijiao(L[i].poe, L[i + 1].poe) == 0)
continue;
L[++cnt] = L[i]; //因为排过序,即使极角相同,后面的也比前面的优
}
L[++cnt] = L[t];

for (int i = 1; i <= cnt; i++) {
while (head < tail && check(q[tail - 1], q[tail], L[i]))
tail--;
while (head < tail && check(q[head + 1], q[head], L[i]))
head++;
q[++tail] = L[i];
}

while (head < tail && check(q[tail - 1], q[tail], q[head]))
tail--;
while (head < tail && check(q[head + 1], q[head], q[tail]))
head++;
}
int main()
{
int n;
cin >> n;

double ans=0;
for (int i = 1; i <= n; i++)
cin >> p[i];
p[n + 1] = p[1];
ans=duobianxingmianji(p,n);

for (int i = 1; i <= n; i++){
l[i] = Line(p[i], p[i + 1]);
l[i].atn2();
}
int t = n;
for (int i = 2; i <= n; i++) {
double a = (p[2] - p[1] - p[i + 1] + p[i]).y;
double b = (p[1] - p[2] - p[i] + p[i + 1]).x;
double c = p[2].x * p[1].y - p[1].x * p[2].y - p[i + 1].x * p[i].y + p[i].x * p[i + 1].y;
if (zhengfu(a) == zhengfu(b) && zhengfu(a) == 0)
continue;
if (zhengfu(a)!=0) {
l[++t] = Line(point(-c / a, 0), point(-c / a + b, -a));
} else if (zhengfu(b)!=0) {
l[++t] = Line(point(0, -c / b), point(b, -c / b - a));
}
l[t].atn2();
}
int head, tail;
banpingmian_jiao(head, tail, l, t);

printf("%.4f\n", solve(head, tail)/ans);

return 0;
}

 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载