社区讨论
63pts WA on#8 9 10 11 求调
P2742【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m3mx2a8o
- 此快照首次捕获于
- 2024/11/18 19:02 去年
- 此快照最后确认于
- 2025/11/04 14:27 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
#define db double
#define xi ps[i].x
#define yi ps[i].y
#define xj ps[j].x
#define yj ps[j].y
#define xk ps[k].x
#define yk ps[k].y
const int N = 100005;
int n, mi, top, ni, q[N];
db my, mx, res;
struct pt
{
db x, y;
db mo()
{
db x1 = mx - x,
y1 = my - y;
return sqrt(x1*x1 + y1*y1);
}
db mop(pt p)
{
return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));
}
bool operator < (pt p)
{
db c = (x-mx) / mo();
db cp = (p.x-mx) / p.mo();
return ((abs(c-cp)) > 5e-4 && c > cp) || (abs(c-cp) <= 5e-4 && mo() < p.mo());
}
} ps[N];
inline bool wp(int i, int j, int k)
{
db x1 = xj - xi,
y1 = yj - yi,
x2 = xk - xj,
y2 = yk - yj;
return (x1*y2 - x2*y1) > -5e-4;
}
signed main()
{
freopen("P2742.txt", "r", stdin);
scanf("%d", &n);
my = (db)INT_MAX;
for (int i = 1; i <= n; ++i) {
scanf("%lf%lf", &xi, &yi);
if (yi < my || (yi == my && xi < mx)) {
mi = i;
my = yi;
mx = xi;
}
}
swap(ps[1], ps[mi]);
sort(ps+2, ps+n+1);
// for (int i = 1; i <= n; ++i) printf("%d %.2lf %.2lf\n\n", i, xi, yi);
q[1] = 1, q[2] = 2, top = 2;
for (ni = 3; ni <= n; ++ni) {
while (!wp(q[top-1], q[top], ni)) q[top--] = 0;
q[++top] = ni;
// for (int i = 1; i <= top; ++i) printf("%d %.2lf %.2lf \n", q[i], ps[q[i]].x, ps[q[i]].y);
// printf("%d\n", ni);
}
// for (int i = 1; i <= n; ++i) printf("%d %lf %lf\n", i, px, py);
// for (int i = 1; i <= top; ++i) printf("%d ", q[i]);
for (int i = 1; i < top; ++i) {
res += ps[q[i]].mop(ps[q[i+1]]);
}
res += ps[q[top]].mop(ps[1]);
if (n >= 2) printf("%.2lf\n", res);
else printf("0.00\n");
// printf("%lf\n", 2 + 3*sqrt(2));
return 0;
}
liangyanbang
回复
共 0 条回复,欢迎继续交流。
正在加载回复...