社区讨论
讲一个很蠢的事情
P2742【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mlnpfdgm
- 此快照首次捕获于
- 2026/02/15 20:11 4 天前
- 此快照最后确认于
- 2026/02/16 15:20 3 天前
这段代码会 WA 掉最后 4 点,你知道为什么吗?
CPP#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n;
struct Point {
float x, y;
Point(float _x = 0, float _y = 0) : x(_x), y(_y) {}
bool operator<(const Point &oth) const {
if (x == oth.x)
return y < oth.y;
return x < oth.x;
}
Point operator-(const Point &oth) const { return {x - oth.x, y - oth.y}; }
} p[N];
float cross(Point a, Point b) { return a.x * b.y - b.x * a.y; }
float cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
float dis(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
float ans = 0;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
float x, y;
cin >> x >> y;
p[i] = {x, y};
}
sort(p + 1, p + n + 1);
vector<int> ups, downs;
for (int i = 1; i <= n; i++) {
while (ups.size() >= 2 &&
cross(p[ups[ups.size() - 2]], p[ups.back()], p[i]) <= 0)
ups.pop_back();
ups.push_back(i);
}
for (int i = n; i >= 1; i--) {
while (downs.size() >= 2 &&
cross(p[downs[downs.size() - 2]], p[downs.back()], p[i]) <= 0)
downs.pop_back();
downs.push_back(i);
}
double ans = 0;
for (size_t i = 0; i + 1 < ups.size(); i++)
ans += dis(p[ups[i]], p[ups[i + 1]]);
for (size_t i = 0; i + 1 < downs.size(); i++)
ans += dis(p[downs[i]], p[downs[i + 1]]);
ans += dis(p[ups[0]], p[downs.back()]);
ans += dis(p[ups.back()], p[downs[0]]);
cout << fixed << setprecision(2) << ans << endl;
return 0;
}
警示后人,float 会爆精度,需要用 double。
回复
共 0 条回复,欢迎继续交流。
正在加载回复...