QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527887#7906. Almost ConvexdechancerTL 4ms19032kbC++2011.3kb2024-08-22 21:43:132024-08-22 21:43:14

Judging History

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

  • [2024-08-22 21:43:14]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:19032kb
  • [2024-08-22 21:43:13]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
using ll = long long;

using ld = double;
constexpr ld eps = 1e-9;
const ld pi = acos(-1.l);

template <class T>
struct Point {
  T x, y;
  Point(T x = 0, T y = 0) : x(x), y(y) {}

  template <class U>
  operator Point<U>() {
    return Point<U>(U(x), U(y));
  }
  Point& operator+=(Point b) { return x += b.x, y += b.y, *this; }
  Point& operator-=(Point b) { return x -= b.x, y -= b.y, *this; }
  Point& operator*=(T t) { return x *= t, y *= t, *this; }
  Point& operator/=(T t) { return x /= t, y /= t, *this; }
  Point operator-() { 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 t) { return a *= t; }
  friend Point operator*(T t, Point b) { return b *= t; }
  friend Point operator/(Point a, T t) { return a /= t; }
  friend Point operator/(T t, Point b) { return b /= t; }
  friend bool operator==(Point a, Point b) { return a.x == b.x and a.y == b.y; }
  friend istream& operator>>(istream& is, Point& a) { return is >> a.x >> a.y; }
  friend ostream& operator<<(ostream& os, Point& a) {
    return os << '(' << a.x << ',' << a.y << ')';
  }
  friend bool operator<(const Point& a, const Point& b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
  }

  int sign() { return y > 0 or (y == 0 and x > 0) ? 1 : -1; }
  T square() { return x * x + y * y; }
  T len() { return sqrt(square()); }
  Point rotate(T r) {
    return Point(x * cos(r) - y * sin(r), x * sin(r) + y * cos(r));
  }

  friend T dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
  friend T dot(Point a, Point b, Point c) { return dot(b - a, c - a); }
  friend T cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
  friend T cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
  friend T dist(Point a, Point b) { return (a - b).len(); }
  friend T angle(Point a, Point b) {
    return acos(dot(a, b) / a.len() / b.len());
  }
  friend bool isParallel(Point a, Point b) { return cross(a, b) == 0; }
  friend bool isPerpendicular(Point a, Point b) { return dot(a, b) == 0; }
  // return the square of dist between the closest points in the plane
  friend T colsestPoint(vector<Point>& a) {
    vector<Point> b(a.size());
    sort(a.begin(), a.end());
    auto divide = [&](auto&& self, auto l, auto r) -> T {
      if (l + 1 == r)
        return LLONG_MAX;

      auto mid = l + (r - l) / 2;
      T midx = mid->x;
      T d = min(self(self, l, mid), self(self, mid, r));
      inplace_merge(l, mid, r, [&](auto& a, auto& b) { return a.y < b.y; });

      b.clear();
      auto square = [](T x) { return x * x; };
      for (auto i = l; i < r; i++) {
        if (square(i->x - midx) < d)
          b.push_back(*i);
      }
      for (int i = 0; i < b.size(); i++) {
        for (int j = i + 1; j < b.size() and square(b[j].y - b[i].y) < d; j++) {
          d = min(d, (b[j] - b[i]).square());
        }
      }
      return d;
    };
    return divide(divide, a.begin(), a.end());
  }
};

template <class T>
struct Line {
  Point<T> a, b;
  Line(Point<T> a = {}, Point<T> b = {}) : a(a), b(b) {}

  friend bool operator<(const Line& u, const Line& v) {
    return u.a != v.a ? u.a < v.a : u.b < v.b;
  }

  Line rotate(T r, Point<T> pivot) {
    return Line(pivot, pivot + (b - a).rotate(r));
  }
  Line getVerticalLine(Point<T> p) { return rotate(pi / 2, p); }
  Line getParallelLine(Point<T> p) { return rotate(0, p); }
  friend bool isParallel(Line u, Line v) {
    return isParallel(u.b - u.a, v.b - v.a);
  }
  friend bool isPerpendicular(Line u, Line v) {
    return isPerpendicular(u.b - u.a, v.b - v.a);
  }
  friend bool isCollinear(Line u, Line v) {
    return cross(u.a, u.b, v.a) == 0 and cross(u.a, u.b, v.b) == 0;
  }
  bool pointOnLine(Point<T> p) { return cross(a, b, p) == 0; }
  bool pointOnLineLeft(Point<T> p) { return cross(a, b, p) > 0; }
  bool pointOnLineRight(Point<T> p) { return cross(a, b, p) < 0; }
  bool pointOnSegment(Point<T> p) {
    return pointOnLine(p) and min(a.x, b.x) <= p.x and p.x <= max(a.x, b.x) and
           min(a.y, b.y) <= p.y and p.y <= max(a.y, b.y);
  }
  friend bool lineIntersectLine(Line u, Line v) { return !isParallel(u, v); }
  friend bool lineIntersectSegment(Line u, Line v) {
    if (isParallel(u, v)) {
      return u.pointOnSegment(v.a) or u.pointOnSegment(v.b);
    }
    return cross(u.b - u.a, v.a - u.a) * cross(u.b - u.a, v.b - u.b) <= 0;
  }
  friend bool segmentIntersectSegment(Line u, Line v) {
    return lineIntersectSegment(u, v) and lineIntersectSegment(v, u);
  }
  T pointToLine(Point<T> p) { return abs(cross(a, b, p)) / (b - a).len(); }
  T pointToSegment(Point<T> p) {
    T res = min(dist(a, p), dist(b, p));
    Line l = getVerticalLine(p);
    if (lineIntersectSegment(l, *this)) {
      res = min(res, pointToLine(p));
    }
    return res;
  }
  friend T segmentToSegment(Line u, Line v) {
    if (segmentIntersectSegment(u, v))
      return 0;
    return min({u.pointToSegment(v.a), u.pointToSegment(v.b),
                v.pointToSegment(u.a), v.pointToSegment(u.b)});
  }
  friend Point<T> intersection(Line u, Line v) {
    return u.a + (u.b - u.a) * (cross(v.b - v.a, u.a - v.a) /
                                cross(v.b - v.a, u.a - u.b));
  }
};

template <class T>
struct Polygon {
  int n;
  vector<Point<T>> p;

  Polygon() {}
  Polygon(int n) { init(n); }

  void init(int n) {
    this->n = n;
    p.assign(n, {});
  }

  void norm() {
    int i = 0;
    for (int j = 0; j < n; j++) {
      if (p[j].y < p[i].y or (p[j].y == p[i].y and p[j].x < p[i].x))
        i = j;
    }
    rotate(p.begin(), p.begin() + i, p.end());
  }
  void polarSort(Point<T> pivot = {}) {
    auto angle = [](auto& a) { return atan2(a.y, a.x); };
    sort(p.begin(), p.end(), [&](auto a, auto b) {
      a -= pivot, b -= pivot;
      return angle(a) < angle(b);
    });
  }
  bool pointInPolygon(Point<T> a) {
    if (cross(p[0], p[1], a) < 0 or cross(p[0], p[n - 1], a) > 0)
      return false;

    int l = 0, r = n - 1;
    while (l < r) {
      int mid = (l + r + 1) / 2;
      if (cross(p[0], p[mid], a) > 0)
        l = mid;
      else
        r = mid - 1;
    }
    Line line(p[l], p[l + 1]);
    return line.pointOnLineLeft(a) or line.pointOnSegment(a);
  }

  friend bool polygonIntersectPolygon(Polygon& a, Polygon& b) {
    return any_of(a.p.begin(), a.p.end(),
                  [&](auto& x) { return b.pointInPolygon(x); }) or
           any_of(b.p.begin(), b.p.end(),
                  [&](auto& x) { return a.pointInPolygon(x); });
  }
  T getPerimeter() {
    T res{};
    for (int i = 0; i < n; i++) {
      res += dist(p[i], p[(i + 1) % n]);
    }
    return res;
  }
  // area shouldn't be taken as abs-val when calcs the center
  // area should be taken as abs-bal when calcs the area
  T getArea() {
    T res{};
    for (int i = 0; i < n; i++) {
      res += cross(p[i], p[(i + 1) % n]);
    }
    return res / 2;
  }
  Point<T> getCenter() {
    Point<T> res;
    T area = getArea();
    if (area == 0)
      return res;

    for (int i = 0; i < n; i++) {
      res += (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
    }
    return res / 6 / area;
  }

  auto& getHull(const T eps = 0) {
    vector<Point<T>> h, stk;
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    h.clear();

    auto stkR = [&](int i) { return stk.rbegin()[i]; };
    auto handle = [&]() {
      stk.clear();
      for (auto& a : p) {
        while (stk.size() >= 2 and cross(stkR(1), stkR(0), a) <= eps) {
          stk.pop_back();
        }
        stk.push_back(a);
      }
      h.insert(h.end(), stk.begin(), stk.end() - 1);
    };
    handle();
    reverse(p.begin(), p.end());
    handle();
    swap(p, h);
    n = p.size();
    return p;
  }
  // shouldn't run getHull at the beginning
  bool isConvex() {
    int prev = n;
    getHull(-eps);
    return prev == n;
  }
  // run getHull first
  auto getAntiPodal() {
    vector ap(n, 0);
    for (int i = 0, j = 1; i < n; i++) {
      auto &a = p[i], &b = p[(i + 1) % n];
      while (cross(a, b, p[j]) < cross(a, b, p[(j + 1) % n])) {
        j = (j + 1) % n;
      }
      ap[i] = j;
    }
    return ap;
  }
  // return the square of diameter
  T getDiameter() {
    T res{};
    auto ap = getAntiPodal();
    for (int i = 0; i < n; i++) {
      res = max(res, (p[ap[i]] - p[i]).square());
    }
    return res;
  }
  auto getRectangularCover() {
    T res = DBL_MAX;
    array<Point<T>, 4> pos;
    auto ap = getAntiPodal();
    for (int i = 0, l = ap[0], r = 0; i < n; i++) {
      auto &a = p[i], b = p[(i + 1) % n];
      while (dot(b, a, p[l]) < dot(b, a, p[(l + 1) % n])) {
        l = (l + 1) % n;
      }
      while (dot(a, b, p[r]) < dot(a, b, p[(r + 1) % n])) {
        r = (r + 1) % n;
      }

      Line D(a, b);
      Line L = D.getVerticalLine(p[l]), R = D.getVerticalLine(p[r]);
      Line U = D.getParallelLine(p[ap[i]]);

      Point<T> lowleft = intersection(L, D), lowright = intersection(R, D);
      Point<T> upleft = intersection(L, U), upright = intersection(R, U);
      T length = dist(lowleft, lowright), width = dist(lowleft, upleft);
      if (length * width < res) {
        res = length * width;
        pos = {lowleft, lowright, upright, upleft};
      }
    }
    return pair(res, pos);
  }
  // run getHull first
  friend auto minkowski(Polygon& a, Polygon& b) {
    a.norm(), b.norm();
    int n = a.p.size(), m = b.p.size();

    vector<Point<T>> res;
    auto &p = a.p, &q = b.p;
    int i = 0, j = 0;
    while (i < n or j < m) {
      res.push_back(p[i % n] + q[j % m]);
      T c = cross(p[(i + 1) % n] - p[i % n], q[(j + 1) % m] - q[j % m]);
      i += c >= 0 and i < n;
      j += c <= 0 and j < m;
    }
    Polygon mk(res.size());
    swap(mk.p, res);
    return mk;
  }

  friend T dist(Polygon a, Polygon b) {
    a.getHull(), b.getHull();
    if (polygonIntersectPolygon(a, b))
      return 0;

    for (auto& p : b.p) {
      p = -p;
    }

    auto mk = minkowski(a, b);
    T res = DBL_MAX;
    for (int i = 0; i < mk.p.size(); i++) {
      Line l(mk.p[i], mk.p[(i + 1) % mk.p.size()]);
      res = min(res, l.pointToSegment({}));
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  vector point(n, Point(0., 0.));
  for (auto& [x, y] : point) {
    cin >> x >> y;
  }

  Polygon<double> poly(n);
  poly.p = point;
  poly.getHull();

  constexpr int maxn = 1e6;
  vector x(maxn * 2 + 1, 0), y(maxn * 2 + 1, 0);
  for (auto& a : poly.p) {
    x[a.x + maxn]++;
    y[a.y + maxn]++;
  }

  auto inhull = [&](Point<double> p) {
    return x[p.x + maxn] and y[p.y + maxn];
  };

  Polygon<double> poly1(n);
  poly1.p = point;

  int ans = 1;
  for (int i = 0; i < n; i++) {
    if (inhull(point[i]))
      continue;

    poly1.polarSort(point[i]);
    auto point1 = poly1.p;
    point1.erase(ranges::find(point1, point[i]));
    for (int j = 0; j < n - 1; j++) {
      ans += inhull(point1[j]) and inhull(point1[(j + 1) % (n - 1)]);
      // cerr << point1[j] << '\n';
    }
  }

  cout << ans;

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 19032kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 4ms
memory: 18960kb

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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:


result: