QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#278470#7906. Almost ConvexjiufengWA 344ms4192kbC++1711.2kb2023-12-07 16:33:072023-12-07 16:33:07

Judging History

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

  • [2023-12-07 16:33:07]
  • 评测
  • 测评结果:WA
  • 用时:344ms
  • 内存:4192kb
  • [2023-12-07 16:33:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else 
#define debug(...) 42
#endif
using T = i64;
const T Eps = 0;
int sign(T a) {
  return a < -Eps ? -1 : a > Eps;
}
int cmp(T a, T b) {
  return sign(a - b);
}
struct Point {
  T x;
  T y;
  Point(T x_ = T(0), T y_ = T(0)) : x(x_), y(y_) {}
  Point &operator+=(Point p) & {
    x += p.x;
    y += p.y;
    return *this;
  }
  Point &operator-=(Point p) & {
    x -= p.x;
    y -= p.y;
    return *this;
  }
  Point &operator*=(T v) & {
    x *= v;
    y *= v;
    return *this;
  }
  Point &operator*=(Point p) & {
    tie(x, y) = pair<T, T>{x * p.x - y * p.y, x * p.y + y * p.x};
    return *this;
  }
  Point &operator/=(Point p) & {
    auto t = p.x * p.x + p.y * p.y;
    tie(x, y) = pair<T, T>{(x * p.x + y * p.y) / t, (y * p.x - x * p.y) / t};
    return *this;
  }
  bool operator<(Point p) const {
    int c = cmp(y, p.y);
    if (c) return c == -1;
    return cmp(x, p.x) == -1;
  }
  Point operator-() const {
    return Point(-x, -y);
  }
  friend Point operator+(Point a, Point b) {
    return a += b;
  }
  friend Point operator-(Point a, Point b) {
    return a -= b;
  }
  friend Point operator*(Point a, T b) {
    return a *= b;
  }
  friend Point operator*(T a, Point b) {
    return b *= a;
  }
  friend Point operator*(Point a, Point b) {
    return a *= b;
  }
  friend Point operator/(Point a, Point b) {
    return a /= b;
  }
  friend bool operator==(Point a, Point b) {
    return a.x == b.x && a.y == b.y;
  }
  friend bool operator!=(Point a, Point b) {
    return !(a == b);
  }
  double at() {
    return atan2(1.0 * y, 1.0 * x);
  }
};
T dot(Point a, Point b) {
  return a.x * b.x + a.y * b.y;
}
// area of triangle with Point(0, 0)
T cross(Point a, Point b) {
  return a.x * b.y - a.y * b.x;
}
T square(Point p) {
  return dot(p, p);
}
double length(Point p) {
  return sqrt(double(square(p)));
}
struct Line {
  Point a;
  Point b;
  Line(Point a_ = Point(), Point b_ = Point()) : a(a_), b(b_) {}
};
Point rotate(Point a) {
  return Point(-a.y, a.x);
} 
int sgn(Point a) {
  return a.y > 0 || (a.y == 0 && a.x > 0) ? 1 : -1;
}
bool pointOnLineLeft(Point p, Line l) {
  return cross(l.b - l.a, p - l.a) > 0;
}
Point lineIntersection(Line l1, Line l2) {
  return l1.a + (l1.b - l1.a) * (cross(l2.b - l2.a, l1.a - l2.a) / cross(l2.b - l2.a, l1.a - l1.b));
}
bool pointOnSegment(Point p, Line l) {
  return cross(p - l.a, l.b - l.a) == T(0) && min(l.a.x, l.b.x) <= p.x && p.x <= max(l.a.x, l.b.x)
    && min(l.a.y, l.b.y) <= p.y && p.y <= max(l.a.y, l.b.y);
}
bool pointInPolygon(Point a, vector<Point> p) {
  int n = p.size();
  for (int i = 0; i < n; i++) {
    if (pointOnSegment(a, Line(p[i], p[(i + 1) % n]))) {
      return true;
    }
  }
  int t = 0;
  for (int i = 0; i < n; i++) {
    auto u = p[i];
    auto v = p[(i + 1) % n];
    if (u.x < a.x && v.x >= a.x && pointOnLineLeft(a, Line(v, u))) {
      t ^= 1;
    }
    if (u.x >= a.x && v.x < a.x && pointOnLineLeft(a, Line(u, v))) {
      t ^= 1;
    }
  }
  return t == 1;
}
// 0 : not intersect
// 1 : strictly intersect
// 2 : overlap
// 3 : intersect at endpoint
tuple<int, Point, Point> segmentIntersection(Line l1, Line l2) {
  if (max(l1.a.x, l1.b.x) < min(l2.a.x, l2.b.x)) {
    return {0, Point(), Point()};
  }
  if (min(l1.a.x, l1.b.x) > max(l2.a.x, l2.b.x)) {
    return {0, Point(), Point()};
  }
  if (max(l1.a.y, l1.b.y) < min(l2.a.y, l2.b.y)) {
    return {0, Point(), Point()};
  }
  if (min(l1.a.y, l1.b.y) > max(l2.a.y, l2.b.y)) {
    return {0, Point(), Point()};
  }
  if (cross(l1.b - l1.a, l2.b - l2.a) == T(0)) {
    if (cross(l1.b - l1.a, l2.a - l1.a) != T(0)) {
      return {0, Point(), Point()};
    } else {
      auto maxx1 = max(l1.a.x, l1.b.x);
      auto minx1 = min(l1.a.x, l1.b.x);
      auto maxy1 = max(l1.a.y, l1.b.y);
      auto miny1 = min(l1.a.y, l1.b.y);
      auto maxx2 = max(l2.a.x, l2.b.x);
      auto minx2 = min(l2.a.x, l2.b.x);
      auto maxy2 = max(l2.a.y, l2.b.y);
      auto miny2 = min(l2.a.y, l2.b.y);
      Point p1(max(minx1, minx2), max(miny1, miny2));
      Point p2(min(maxx1, maxx2), min(maxy1, maxy2));
      if (!pointOnSegment(p1, l1)) {
        swap(p1.y, p2.y);
      }
      if (p1 == p2) {
        return {3, p1, p2};
      } else {
        return {2, p1, p2};
      }
    }
  }
  auto cp1 = cross(l2.a - l1.a, l2.b - l1.a);
  auto cp2 = cross(l2.a - l1.b, l2.b - l1.b);
  auto cp3 = cross(l1.a - l2.a, l1.b - l2.a);
  auto cp4 = cross(l1.a - l2.b, l1.b - l2.b);
  if ((cp1 > T(0) && cp2 > T(0)) || (cp1 < T(0) && cp2 < T(0)) || (cp3 > T(0) && cp4 > T(0)) || (cp3 < T(0) && cp4 < T(0))) {
    return {0, Point(), Point()};
  }
  Point p = lineIntersection(l1, l2);
  if (cp1 != T(0) && cp2 != T(0) && cp3 != T(0) && cp4 != T(0)) {
    return {1, p, p};
  } else {
    return {3, p, p};
  }
}
bool segmentInPolygon(Line l, vector<Point> p) {
  int n = p.size();
  if (!pointInPolygon(l.a, p)) {
    return false;
  }
  if (!pointInPolygon(l.b, p)) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    auto u = p[i];
    auto v = p[(i + 1) % n];
    auto w = p[(i + 2) % n];
    auto [t, p1, p2] = segmentIntersection(l, Line(u, v));
    if (t == 1) {
      return false;
    }
    if (t == 0) {
      continue;
    }
    if (t == 2) {
      if (pointOnSegment(v, l) && v != l.a && v != l.b) {
        if (cross(v - u, w - v) > 0) {
          return false;
        }
      }
    } else {
      if (p1 != u && p1 != v) {
        if (pointOnLineLeft(l.a, Line(v, u))
          || pointOnLineLeft(l.b, Line(v, u))) {
          return false;
        }
      } else if (p1 == v) {
        if (l.a == v) {
          if (pointOnLineLeft(u, l)) {
            if (pointOnLineLeft(w, l)
              && pointOnLineLeft(w, Line(u, v))) {
              return false;
            }
          } else {
            if (pointOnLineLeft(w, l)
              || pointOnLineLeft(w, Line(u, v))) {
              return false;
            }
          }
        } else if (l.b == v) {
          if (pointOnLineLeft(u, Line(l.b, l.a))) {
            if (pointOnLineLeft(w, Line(l.b, l.a))
              && pointOnLineLeft(w, Line(u, v))) {
              return false;
            }
          } else {
            if (pointOnLineLeft(w, Line(l.b, l.a))
              || pointOnLineLeft(w, Line(u, v))) {
              return false;
            }
          }
        } else {
          if (pointOnLineLeft(u, l)) {
            if (pointOnLineLeft(w, Line(l.b, l.a))
              || pointOnLineLeft(w, Line(u, v))) {
              return false;
            }
          } else {
            if (pointOnLineLeft(w, l)
              || pointOnLineLeft(w, Line(u, v))) {
              return false;
            }
          }
        }
      }
    }
  }
  return true;
}
vector<Point> hp(vector<Line> lines) {
  sort(lines.begin(), lines.end(), [&](auto l1, auto l2) {
    auto d1 = l1.b - l1.a;
    auto d2 = l2.b - l2.a;
    if (sgn(d1) != sgn(d2)) {
      return sgn(d1) == 1;
    }
    return cross(d1, d2) > 0;
  });
  deque<Line> ls;
  deque<Point> ps;
  for (auto l : lines) {
    if (ls.empty()) {
      ls.push_back(l);
      continue;
    }
    while (!ps.empty() && !pointOnLineLeft(ps.back(), l)) {
      ps.pop_back();
      ls.pop_back();
    }
    while (!ps.empty() && !pointOnLineLeft(ps[0], l)) {
      ps.pop_front();
      ls.pop_front();
    }
    if (cross(l.b - l.a, ls.back().b - ls.back().a) == 0) {
      if (dot(l.b - l.a, ls.back().b - ls.back().a) > 0) {
        if (!pointOnLineLeft(ls.back().a, l)) {
          assert(ls.size() == 1);
          ls[0] = l;
        }
        continue;
      }
      return {};
    }
    ps.push_back(lineIntersection(ls.back(), l));
    ls.push_back(l);
  }
  while (!ps.empty() && !pointOnLineLeft(ps.back(), ls[0])) {
    ps.pop_back();
    ls.pop_back();
  }
  if (ls.size() <= 2) {
    return {};
  }
  ps.push_back(lineIntersection(ls[0], ls.back()));
  return vector<Point>(ps.begin(), ps.end());
}
T crossA(Point a, Point b, Point c) {
  return cross(b - a, c - a);
}
T crossOp(Point a, Point b, Point c) {
  return sign(crossA(a, b, c));
}
vector<Point> converHull(vector<Point> p) {
  int n = p.size();
  if (n < 2) return p;
  // sort(p.begin(), p.end(), [&](Point a, Point b) {
  //   if (a.x == b.x) {
  //     return a.x < b.x;
  //   } else {
  //     return a.y < b.y;
  //   }
  // });
  sort(p.begin(), p.end());
  vector<Point> q(2 * n);
  int k = 0;
  for (int i = 0; i < n; q[k++] = p[i++]) {
    while (k > 1 && crossOp(q[k - 2], q[k - 1], p[i]) <= 0) {
      k--;
    }
  } 
  for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--]) {
    while (k > t && crossOp(q[k - 2], q[k - 1], p[i]) <= 0) {
      k--;
    }
  }
  q.resize(k - 1);
  return q;
}
// need to unique the first
vector<Point> converHullNonStrict(vector<Point> p) {
  int n = p.size();
  if (n < 2) return p;
  sort(p.begin(), p.end(), [&](Point a, Point b) {
    if (a.x == b.x) {
      return a.x < b.x;
    } else {
      return a.y < b.y;
    }
  });
  vector<Point> q(2 * n);
  int k = 0;
  for (int i = 0; i < n; q[k++] = p[i++]) {
    while (k > 1 && crossOp(q[k - 2], q[k - 1], p[i]) < 0) {
      k--;
    }
  } 
  for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--]) {
    while (k > t && crossOp(q[k - 2], q[k - 1], p[i]) < 0) {
      k--;
    }
  }
  q.resize(k - 1);
  return q;
}
T area(vector<Point> p) {
  int n = (int) p.size();
  sort(p.begin(), p.end(), [&](Point a, Point b) {
    return atan2(a.y, a.x) < atan2(b.y, b.x);
  });
  T ans = 0;
  for (int i = 0; i < n; i++) {
    ans += cross(p[i], p[(i + 1) % n]);
  }
  return ans / 2;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<Point> p(n);
  for (int i = 0; i < n; i++) {
    T x, y;
    cin >> x >> y;
    p[i] = Point(x, y);
  }
  auto q = converHull(p);
  set<Point> s(q.begin(), q.end());
  vector<bool> inhull(n);
  for (int i = 0; i < n; i++) {
    if (s.count(p[i])) {
      inhull[i] = true;
    }
  }
  if ((int) q.size() == n) {
    cout << "1\n";
    return 0;
  }
  function<int(int)> calc = [&](int s) {
    vector<pair<Point, int>> v;
    vector<double> at(n);
    for (int i = 0; i < n; i++) {
      if (i == s) continue;
      v.emplace_back(p[i] - p[s], i);
      at[i] = v.back().first.at();
    }
    sort(v.begin(), v.end(), [&](auto a, auto b) {
      return at[a.second] < at[b.second];
    });
    int fi = 0, ls = n - 2;
    while (inhull[v[fi].second]) {
      fi++;
    }
    while (inhull[v[ls].second]) {
      ls--;
    }
    int cnt = fi + n - 2 - ls - 1;
    for (int i = fi, j = fi; i <= ls; i = j) {
      j = i + 1;
      while (j <= ls && inhull[v[i].second] && inhull[v[j].second]) {
        j++;
      }
      if (inhull[v[i].second]) {
        cnt += j - i - 1;
      }
    }
    return cnt;
  };
  i64 ans = 1;
  for (int i = 0; i < n; i++) {
    if (inhull[i]) continue;
    ans += calc(i);
  }
  cout << ans << '\n';
  return 0; 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 344ms
memory: 4180kb

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:

-967

result:

wrong answer 1st numbers differ - expected: '718', found: '-967'