QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#730292#9520. Concave HullDBsoleil#WA 31ms3956kbC++232.9kb2024-11-09 19:34:282024-11-09 19:34:28

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 19:34:28]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:3956kb
  • [2024-11-09 19:34:28]
  • 提交

answer


#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 1e5 + 5;
using int_t = int64_t;
using real_t = long double;
struct point {
  int_t x, y;
  point() { }
  point(int_t x, int_t y) : x(x), y(y) { }
  friend point operator + (const point &lhs, const point &rhs) { return point(lhs.x + rhs.x, lhs.y + rhs.y); }
  friend point operator - (const point &lhs, const point &rhs) { return point(lhs.x - rhs.x, lhs.y - rhs.y); }
  friend int_t operator * (const point &lhs, const point &rhs) { return lhs.x * rhs.x + lhs.y * rhs.y; }
  int_t abs(void) const { return x * x + y * y; }
  friend bool operator < (const point &lhs, const point &rhs) { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y); }
}; int_t det(const point &a, const point &b) { return a.x * b.y - a.y * b.x; }
int_t area2(const point &a, const point &b, const point &c) { return abs(det(b - a, c - a)); }
int sgn(int_t x) { return x == 0 ? 0 : (x > 0 ? 1 : -1); }
real_t distance(point p, point x, point y) { return abs((real_t)det(y - x, p - x) / (y - x).abs()); }
bool turn_left(const point &a, const point &b, const point &c)
{ return sgn(det(b - a, c - a)) >= 0; }
vector<point> convex_hull(vector<point> a) {
  int n = (int)a.size(), cnt = 0;
  if (n < 2) return a;
  sort(a.begin(), a.end(), [&](auto lhs, auto rhs)
      { return make_pair(lhs.x, lhs.y) < make_pair(rhs.x, rhs.y); });
  vector<point> ret;
  for (int i = 0; i < n; ++i) {
    while (cnt > 1 && turn_left(ret[cnt - 2], a[i], ret[cnt - 1]))
      --cnt, ret.pop_back();
    ++cnt, ret.push_back(a[i]);
  } int fixed = cnt;
  for (int i = n - 2; i >= 0; --i) {
    while (cnt > fixed && turn_left(ret[cnt - 2], a[i], ret[cnt - 1]))
      --cnt, ret.pop_back();
    ++cnt, ret.push_back(a[i]);
  } ret.pop_back(); return ret;
} // convex_hull
int_t calc_area(const vector<point> &a) {
  int_t ret = 0;
  for (int i = 1; i < (int)a.size() - 1; ++i)
    ret += area2(a[0], a[i], a[i + 1]);
  return ret;
} // calc_area
int main(void) {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tests; cin >> tests;
  while (tests--) {
    int n; cin >> n; vector<point> a(n), c;
    for (auto &[x, y]: a) cin >> x >> y;
    auto b = convex_hull(a); set<point> sb;
    auto area = calc_area(b);
    for (auto z: b) sb.insert(z);
    for (auto z: a) if (sb.find(z) == sb.end()) c.push_back(z);
    if (c.empty()) { cout << "-1\n"; continue; }
    auto d = convex_hull(c); int p = 0;
    for (int i = 0; i < (int)d.size(); ++i)
      if (distance(d[i], b[0], b[1]) < distance(d[p], b[0], b[1])) p = i;
    auto tri = area2(d[p], b[0], b[1]);
    for (int i = 1, q = p; i < (int)b.size(); ++i) {
      point x = b[i], y = b[(i + 1) % (int)b.size()];
      while (distance(d[(q + 1) % (int)d.size()], x, y) <= distance(d[q], x, y)) ++q;
      tri = min(tri, area2(d[q], x, y));
    } cout << area - tri << endl;
  }
  return 0;
} // main

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3564kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

40
-1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

2178418010787347715
1826413114144932145
1651687576234220014
1883871859778998985
2119126281997959892
894016174881844630
2271191316922158910
1998643358049669416
1740474221286618711
1168195646932543192

result:

ok 10 lines

Test #3:

score: -100
Wrong Answer
time: 31ms
memory: 3956kb

input:

1000
125
64661186 -13143076
302828013 -185438065
-418713797 -191594241
430218126 -397441626
354327250 -836704374
149668812 -598584998
311305970 66790541
199720625 -592356787
468137 -584752683
258775829 96211747
-358669612 -134890109
-129221188 -998432368
-277309896 -140056561
356901185 420557649
-51...

output:

1986320445246155278
1900093336073022078
1612088392301142476
2012259136539173407
1819942017252118749
1772230185841892196
1164835025329039520
1527446155241140517
1807368432185303666
1236918659444944569
1306839249967484778
1984123720246784099
1868728080720036006
667458140583450322
2127932992585026491
4...

result:

wrong answer 16th lines differ - expected: '447172929227332597', found: '480128762112500892'