QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743570#9520. Concave HullgjlcccWA 1ms3600kbC++203.2kb2024-11-13 19:31:522024-11-13 19:31:53

Judging History

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

  • [2024-11-13 19:31:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3600kb
  • [2024-11-13 19:31:52]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct Point {
  int x, y, idx;
  bool operator<(const Point &b) const { return x == b.x ? y < b.y : x < b.x; }
  friend Point operator-(Point a, Point b) { return {a.x - b.x, a.y - b.y}; }
};
ll vis[N];
ll cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
ll cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
ll dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
// Point operator-(Point a, Point b) { return {a.x - b.x, a.y - b.y}; }
// Point operator+(Point a, Point b) { return {a.x + b.x, a.y + b.y}; }
// Point operator*(Point a, ll b) { return {a.x * b, a.y * b}; }
// Point operator/(Point a, ll b) { return {a.x / b, a.y / b}; }
// ll dis(Point a) { return a.x * a.x + a.y * a.y; }
// ll dis(Point a, Point b) { return dis(a - b); }
vector<Point> a1, con1, con2, a2;
vector<Point> get_hull(vector<Point> &a) {
  ll n = a.size();
  if (n <= 2) {
    return a;
  }
  vector<Point> ans(n * 2);
  sort(a.begin(), a.end());
  int now = -1;
  for (ll i = 0; i < n; i++) {
    while (now > 0 && cross(a[i], ans[now], ans[now - 1]) <= 0) {
      now--;
    }
    ans[++now] = a[i];
  }
  int pre = now;
  for (ll i = n - 2; i >= 0; i--) {
    while (now > pre && cross(a[i], ans[now], ans[now - 1]) <= 0) {
      now--;
    }
    ans[++now] = a[i];
  }
  ans.resize(now);
  return ans;
}
void solve() {
  ll n;
  a1.clear();
  a2.clear();
  con1.clear();
  con2.clear();
  cin >> n;
  for (ll i = 1; i <= n; i++) vis[i] = 0;
  for (ll i = 1; i <= n; i++) {
    ll x, y;
    cin >> x >> y;
    a1.emplace_back((Point){x, y, i});
    // cout << a1[i - 1].x << " " << a1[i - 1].y << "  " << a1[i - 1].idx <<
    // endl;
  }
  //   sort(a1.begin(), a1.end());
  con1 = get_hull(a1);
  for (auto aaa : con1) {
    vis[aaa.idx] = 1;
  }
  if (con1.size() == n) {
    cout << -1 << "\n";
    return;
  }
  for (auto aaa : a1) {
    if (vis[aaa.idx] == 0) {
      a2.push_back(aaa);
    }
  }
  reverse(con1.begin(), con1.end());
  con2 = get_hull(a2);
  reverse(con2.begin(), con2.end());

  ll ans = 0;
  ll l = 0, r = 0;
  ll len1 = con1.size();
  ll len2 = con2.size();
  for (ll i = 0; i < len1; i++) {
    ans = ans + cross(con1[i], con1[(i + 1) % len1]);
  }

  //   for (auto aaa : con1) {
  //     cout << aaa.x << " " << aaa.y << endl;
  //   }
  //   cout << "\n";
  //   for (auto aaa : con2) {
  //     cout << aaa.x << " " << aaa.y << endl;
  //   }
  ans = abs(ans);
  ll tmp = 1e18;
  // cout << abs(cross(con1[0], con1[1], con2[1])) << endl;
  for (ll i = 0; i < len1; i++) {
    while (cross(con1[i], con1[(i + 1) % len1], con2[(r + 1) % len2]) <
           cross(con1[i], con1[(i + 1) % len1], con2[r])) {
      r = (r + 1) % len2;
    }
    // cout << abs(get_thr_p_area(con1[i], con1[(i + 1) % len1], con2[r])) <<
    // endl;
    tmp = min(tmp, abs(cross(con1[i], con1[(i + 1) % len1], con2[r])));
    // cout << tmp << endl;
  }
  cout << ans - tmp << "\n";
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll t = 1;
  cin >> t;
  while (t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
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:

10337402351
1736537664
2024061003
6498155794
8955700191
2255545308
131733416
4850012323
-795159809
943828458

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: '10337402351'