社区讨论

讲一个很蠢的事情

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 条回复,欢迎继续交流。

正在加载回复...