QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402448#7693. Convex Hull Extensionu2x1WA 1ms3780kbC++203.6kb2024-04-30 16:28:362024-04-30 16:28:36

Judging History

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

  • [2024-04-30 16:28:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3780kb
  • [2024-04-30 16:28:36]
  • 提交

answer

#include "bits/stdc++.h"

#define all(x)   x.begin(), x.end()
#define NL       std::cout << '\n'

using lnt = long long;

const int inf = 0x3f3f3f3f;
const lnt linf = 1ll << 62;

using db = long double;
const db eps = 1e-15;
int sgn(db x) { return (x < -eps ? -1 : x > eps); }


struct Pt { db x, y; };
Pt readpt() { int x, y; std::cin >> x >> y; Pt p; p.x = x; p.y = y; return p; }
void printpt(Pt p) { std::cout << "(" << p.x << "," << p.y << ")"; }
Pt operator-(Pt a, Pt b) { return { a.x - b.x, a.y - b.y }; }
Pt operator+(Pt a, Pt b) { return { a.x + b.x, a.y + b.y }; }
Pt operator*(Pt a, db x) { return { a.x * x, a.y * x }; }
Pt operator/(Pt a, db x) { return { a.x / x, a.y / x }; }
db dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
db det(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
bool operator==(Pt a, Pt b) { return !sgn(dot(a-b, a-b)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
db dis2(Pt a, Pt b) { return dot(a-b, a-b); }
db dis(Pt a, Pt b) { return std::sqrt(dis2(a, b)); }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }

struct Line { Pt s, t; };
Pt intersect(Line a, Line b) {
  db v = det(a.t - a.s, b.s - a.s);
  db u = det(a.t - a.s, b.t - a.s);
  return (b.s * u - b.t * v) / (u - v);
}
bool para(Line a, Line b) { return !sgn(det(a.t - a.s, b.t - b.s)); }

struct Seg { Pt s, t; };
lnt ptCntOnSeg(Seg p) {
  lnt dx = ((p.t - p.s).x), dy = ((p.t - p.s).y);
  dx = dx < 0 ? -dx : dx; 
  dy = dy < 0 ? -dy : dy; 
  return std::gcd(dx, dy) + 1;
}

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  auto hasInf = []() { std::cout << "infinitely many"; exit(0); };
  int n; std::cin >> n;
  std::vector<Pt> v(n);
  for (int i = 0; i < n; ++i) { v[i] = readpt(); }
  lnt ret = 0;
  for (int i = 0; i < n; ++i) {
    auto l = v[i], r = v[(i+1) % n];
    auto l1 = v[i ? i-1 : n-1], r1 = v[(i+2) % n];
    if (sgn(det(l - l1, r - r1)) >= 0) {
      std::vector<Pt> hull { l, l + (l - l1) * 2500 * 2500, r + (r - r1) * 2500 * 2500, r };
      db s = 0; int c = 0;
      for (int i = 0; i < hull.size(); ++i) {
        s += det(hull[i], hull[(i+1) % hull.size()]);
        c += ptCntOnSeg({hull[i], hull[(i+1) % hull.size()]}) - 1; 
      }
      if ((lnt)std::floor(s+eps) / 2 - c / 2 + 1 + (ptCntOnSeg({hull[1], hull[2]}) - 2) > 0) {
        hasInf();
      }
      continue;
    }
    auto inter = intersect({l1, l}, {r, r1});
    lnt kl = std::floor(eps + std::sqrt(dis2(inter, l) / dis2(l, l1)));
    lnt kr = std::floor(eps + std::sqrt(dis2(inter, r) / dis2(r, r1)));
    std::vector<Pt> tri;
    if (kl || kr) {
      std::vector<Pt> hull= {l, (l + (l - l1) * kl), (r + (r - r1) * kr), r};
      db s = 0; int c = 0;
      for (int i = 0; i < hull.size(); ++i) {
        s += det(hull[i], hull[(i+1) % hull.size()]);
        c += ptCntOnSeg({hull[i], hull[(i+1) % hull.size()]}) - 1; 
      }
      ret += (lnt)std::floor(s+eps) / 2 - c / 2 + 1 + (ptCntOnSeg({hull[1], hull[2]}) - 2);
      tri = {hull[1], inter, hull[2]};
    } else {
      tri = {l, inter, r};
    }
    db mix = inf, mxx = -inf, miy = inf, mxy = -inf;
    for (auto p : tri) {
      mix = std::min(mix, p.x); miy = std::min(miy, p.y);
      mxx = std::max(mxx, p.x); mxy = std::max(mxy, p.y);
    }
    for (int x = mix - 1; x <= mxx + 1; ++x) {
      for (int y = miy - 1; y <= mxy + 1; ++y) {
        Pt p {(db)x, (db)y};
        ret += side(tri[0], tri[1], p) > 0 && side(tri[1], tri[2], p) > 0 && side(tri[2], tri[0], p) > 0;
      }
    }
  }
  std::cout << ret;
  
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3560kb

input:

5
0 2
-2 0
-1 -3
1 -3
2 1

output:

23

result:

ok single line: '23'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

4
-7 -7
7 -7
7 7
-7 7

output:

infinitely many

result:

ok single line: 'infinitely many'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

4
-1000 1000
-1000 999
-999 999
-999 1000

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3452kb

input:

6
0 -901
900 -900
900 900
0 901
-900 900
-900 -900

output:

1458000000

result:

wrong answer 1st lines differ - expected: '1457999998', found: '1458000000'