- 开头:
#include<bits/stdc++.h>
using namespace std;
#define Re register int
typedef double dl;
const dl eps = 1e-10;
- 向量表示:
struct vet
{
dl x, y;
};
- 直线表示
struct li
{
vet a, b;//a为起点,b为向量
};
- 线段表示
struct li
{
vet a, b;//a为起点,b为终点
};
- 基础运算
inline vet operator + (vet x, vet y)//向量+向量
{
return vet{x.x + y.x, x.y + y.y};
}
inline vet operator - (vet x, vet y)//向量-向量
{
return vet{x.x - y.x, x.y - y.y};
}
inline vet operator * (vet x, dl y)//向量*某个值
{
return vet{x.x * y, x.y * y};
}
inline vet operator / (vet x, dl y)//向量/某个值
{
return vet{x.x / y, x.y / y};
}
inline dl cj(vet x, vet y)//叉积
{
return x.x * y.y - x.y * y.x;
}
inline dl dj(vet x, vet y)//点积
{
return x.x * y.x + x.y * y.y;
}
- 求模长
inline dl len(vet x)
{
return sqrt(x.x * x.x + x.y * x.y);
}
- 判断三点是否共线
inline bool check_gx(vet x, vet y, vet z)
{
return abs(cj(y - x, z - x)) < eps;
}
- 判断某个点是否在一条有向直线的右侧(左侧同理)
inline bool check_right(li x, vet y)
{
return cj(y - x.a, x.b) > -eps;
}
- 两直线求交
inline vet find_id(li x, li y)
{
dl z = cj(x.a - y.a, y.b) / cj(y.b, x.b);
return x.a + x.b * z;
}
- 多边形面积
inline dl get_S()
{
dl S = 0;
for (Re i = 1; i <= n; ++i) S += cj(d[i], d[i > 1 ? i - 1 : n]);//d[i]为多边形按顺时针或逆时针依次经过的顶点坐标,类型为vet
if (S < 0) S = -S;
return 0.5 * S;
}
- \(\mathcal O(log\ n)\)判断一个点是否在一个凸包的内部
inline bool check(vet x)//凸包上的点编号为0~n,c数组为凸包上的每个点代表的坐标向量减去上一个点的坐标向量,其中c[0]为最下面的点中最靠左的点,c[0]没有被处理
{
x = x - c[0];
if (cj(x, c[1]) > eps || cj(x, c[n]) < -eps) return 0;
int l = 2, r = n - 1, s = 1;
while (l <= r)
{
int mid = l + r >> 1;
if (cj(c[mid], x) > -eps) s = mid, l = mid + 1;
else r = mid - 1;
}
return cj(c[s] - x, c[s + 1] - x) > -eps;
}
-
凸包(Graham扫描法)[USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包(只有以前的代码,码风太丑了,先鸽着)
-
半平面交(S&I算法)[CQOI2006]凸多边形 /【模板】半平面交
#include<bits/stdc++.h>
using namespace std;
#define Re register int
typedef double dl;
const int N = 505;
const dl eps = 1e-10;
struct vet
{
dl x, y;
}q[N];
struct li
{
vet a, b;
dl ang;
}d[N];
int n, m, num, l = 1, r, g[N];
dl ans;
inline int read()
{
char c = getchar();
int ans = 0;
bool f = 1;
while (c < 48 || c > 57)
{
if (c == '-') f = 0;
c = getchar();
}
while (c >= 48 && c <= 57) ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
return f ? ans : -ans;
}
inline vet operator + (vet x, vet y)
{
return vet{x.x + y.x, x.y + y.y};
}
inline vet operator - (vet x, vet y)
{
return vet{x.x - y.x, x.y - y.y};
}
inline vet operator * (vet x, dl y)
{
return vet{x.x * y, x.y * y};
}
inline dl cj(vet x, vet y)
{
return x.x * y.y - x.y * y.x;
}
inline li make_line(vet x, vet y)
{
vet z = y - x;
return li{x, z, atan2(z.y, z.x)};
}
inline vet find_id(li x, li y)
{
dl z = cj(x.a - y.a, y.b) / cj(y.b, x.b);
return x.a + x.b * z;
}
inline bool cmp(li x, li y)
{
return abs(x.ang - y.ang) > eps ? x.ang < y.ang : cj(y.a - x.a, x.b) > eps;
}
int main()
{
n = read();
while (n--)
{
m = read();
for (Re i = 1; i <= m; ++i) q[i].x = read(), q[i].y = read();
for (Re i = 1; i <= m; ++i) d[++num] = make_line(q[i], q[(i > 1) ? i - 1 : m]);
}
sort(d + 1, d + num + 1, cmp);
for (Re i = 1; i <= num; ++i)
{
if (i > 1 && abs(d[i].ang - d[i - 1].ang) < eps && abs(cj(d[i - 1].a - d[i].a, d[i].b)) < eps) continue;
while (l < r && cj(q[r - 1] - d[i].a, d[i].b) < -eps) --r;
while (l < r && cj(q[l] - d[i].a, d[i].b) < -eps) ++l;
if (l <= r && abs(d[i].ang - d[g[r]].ang) < eps)
{
li u = d[i], v = d[g[r]];
if (cj(u.a - v.a, v.b) > eps && cj(v.a - u.a, u.b) > eps)
{
printf("0.000");
return 0;
}
--r;
}
g[++r] = i;
if (l < r) q[r - 1] = find_id(d[g[r - 1]], d[i]);
}
while (l < r && cj(q[r - 1] - d[g[l]].a, d[g[l]].b) < -eps) --r;
if (r < l + 2) printf("0.000");
else
{
q[r] = find_id(d[g[l]], d[g[r]]);
for (Re i = l; i <= r; ++i)
{
int u = (i ^ l) ? i - 1 : r, v = (i ^ r) ? i + 1 : l;
ans += cj(q[i], q[v]);
}
if (ans < -eps) ans = -ans;
printf("%.3lf", 0.5 * ans);
}
return 0;
}