QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402419#7693. Convex Hull Extensionu2x1WA 1ms3840kbC++203.5kb2024-04-30 15:38:492024-04-30 15:38:51

Judging History

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

  • [2024-04-30 15:38:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2024-04-30 15:38:49]
  • 提交

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-12;
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)); }
db area(Pt a, Pt b, Pt c) { return std::abs(det(a - b, a - c)); }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
Pt rot90(Pt a) { return {-a.y, a.x}; }
Pt unit(Pt a) {
  db d = dis(a, {0, 0});
  return sgn(d) ? a/d : Pt{0, 0};
}

struct Line { Pt s, t; };
db pt2line(Pt x, Line l) {
  if (l.s == l.t) { return dis(l.s, x); }
  return std::abs(det(x - l.s, x - l.t) / dis(l.s, l.t));
}
bool ptonline(Pt x, Line l) {
  if (l.s == l.t) { return sgn(dis2(l.s, x)) == 0; }
  return sgn(det(l.s - x, l.t - x)) == 0;
}
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 = std::abs((p.t - p.s).x), dy = std::abs((p.t - p.s).y);
  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 (para({l1, l}, {r1, r})) { hasInf(); }
    auto inter = intersect({l1, l}, {r, r1});
    if (side(l, r, inter) == 1) { hasInf(); }
    db k = (inter.x - r.x) / (r.x - r1.x);
    int fk = std::floor(k + eps);
    std::vector<Pt> hull({l, r});
    std::vector<Pt> tri;
    if (fk != 0) {
      hull= {l, (l + (l - l1) * fk), (r + (r - r1) * fk), 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: 3652kb

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: 3552kb

input:

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

output:

infinitely many

result:

ok single line: 'infinitely many'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3840kb

input:

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

output:

infinitely many

result:

wrong answer 1st lines differ - expected: '0', found: 'infinitely many'