【SCOI2015】小凸想跑步

时间：2022-08-09 03:44:27

题面

题解

推波柿子：

【SCOI2015】小凸想跑步

设点\(A(x_a, y_a), B(x_b, y_b), C(x_c, y_c), D(x_d, y_d), P(x, y)\)

\(\vec{a} = (x_b - x_a, y_b - y_a), \vec{b} = (x_d - x_c, y_d - y_c)\)

\(\overrightarrow{AP} = (x - x_a, y - y_a), \overrightarrow{CP} = (x - x_c, y - y_c)\)

\(\vec{a} \times \overrightarrow{AP} = (x_b - x_a)(y - y_a) - (x_b - y_a)(x - x_a)\)

\(\vec{b} \times \overrightarrow{CP} = (x_d - x_c)(y - y_c) - (y_d - y_c)(x - x_c)\)

由题目，\(\vec{a} \times \overrightarrow{AP} < \vec{b} \times \overrightarrow{CP}\)，那么有

\[\begin{aligned}
&(x_b - x_a)(y - y_a) - (x_b - y_a)(x - x_a) < (x_d - x_c)(y - y_c) - (y_d - y_c)(x - x_c) \\
\Rightarrow & (x_b - x_a + x_d - x_c)y - (y_b - y_a - y_d + y_c)x + (y_b x_a - x_b y_a + y_d x_c - x_d y_c) < 0
\end{aligned}
\]

然后这个就是一个裸的半平面交了。

代码

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cmath>

#include<algorithm>

#define RG register

#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define clear(x, y) memset(x, y, sizeof(x))

inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while(ch != '-' && (!isdigit(ch))) ch = getchar();

	if(ch == '-') w = -1, ch = getchar();

	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}

const int maxn(200010);

struct point { double x, y; } p[maxn];

struct line { point x, y; double ang; } L[maxn];

typedef point vector;

inline vector operator + (const vector &lhs, const vector &rhs)

	{ return (vector) {lhs.x + rhs.x, lhs.y + rhs.y}; }

inline vector operator - (const vector &lhs, const vector &rhs)

	{ return (vector) {lhs.x - rhs.x, lhs.y - rhs.y}; }

inline vector operator * (const vector &lhs, const double &rhs)

	{ return (vector) {lhs.x * rhs,   lhs.y * rhs};   }

inline double operator * (const vector &lhs, const vector &rhs)

	{ return lhs.x * rhs.x + lhs.y * rhs.y; }

inline double cross(const vector &lhs, const vector &rhs)

	{ return lhs.x * rhs.y - lhs.y * rhs.x; }

inline line make_line(const point &x, const point &y)

	{ return (line) {x, y, atan2(y.y, y.x)}; }

inline bool operator < (const line &lhs, const line &rhs)

	{ return lhs.ang < rhs.ang; }

inline bool isLeft(const point &a, const line &b)

	{ return cross(b.y, (a - b.x)) > 0; }

point Intersection(const line &a, const line &b)

	{ return a.x + a.y * (cross(b.y, b.x - a.x) / cross(b.y, a.y)); }

int n, m;

double Area, ans;

void HalfPlane()

{

	int l, r = 1; std::sort(L + 1, L + m + 1);

	for(RG int i = 2; i <= m; i++)

		if(L[i].ang != L[r].ang) L[++r] = L[i];

		else if(isLeft(L[i].x, L[r])) L[r] = L[i];

	m = r, l = r = 1;

	for(RG int i = 2; i <= m; i++)

	{

		while(l < r && !isLeft(p[r], L[i])) --r;

		while(l < r && !isLeft(p[l + 1], L[i])) ++l;

		L[++r] = L[i];

		if(l < r) p[r] = Intersection(L[r], L[r - 1]);

	}

	while(l < r && !isLeft(p[r], L[l])) --r;

	p[l] = p[r + 1] = Intersection(L[r], L[l]);

	for(RG int i = l; i <= r; i++) ans += cross(p[i], p[i + 1]);

	ans /= Area;

}

int main()

{

	n = read();

	for(RG int i = 0; i < n; i++)

		p[i] = (point) {(double)read(), (double)read()};

	p[n] = p[0];

	for(RG int i = 0; i < n; i++)

		L[++m] = make_line(p[i], p[i + 1] - p[i]),

		Area += cross(p[i], p[i + 1]);

	for(RG int i = 1; i < n; i++)

	{

		double a = p[1].x - p[0].x + p[i].x - p[i + 1].x;

		double b = p[1].y - p[0].y + p[i].y - p[i + 1].y;

		double c = p[1].x * p[0].y + p[i].x * p[i + 1].y

			- p[0].x * p[1].y - p[i + 1].x * p[i].y;

		if(a) L[++m] = make_line((point) {0, c / a}, (point) {-a, -b});

		else if(b) L[++m] = make_line((point) {-c / b, 0}, (point) {0, -b});

	}

	HalfPlane();

	printf("%.4lf\n", ans);

	return 0;

}

相关文章