結果
問題 | No.2331 Maximum Quadrilateral |
ユーザー |
👑 ![]() |
提出日時 | 2023-05-28 15:14:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 453 ms / 2,000 ms |
コード長 | 8,798 bytes |
コンパイル時間 | 5,459 ms |
コンパイル使用メモリ | 267,768 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-27 05:30:39 |
合計ジャッジ時間 | 12,351 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 998244353;// constexpr int MOD = 1000000007;constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U>inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U>inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;namespace geometry {using Integer = long long;int sgn(const Integer x) {return x > 0 ? 1 : (x < 0 ? -1 : 0);}struct Point {Integer x, y;explicit Point(const Integer x = 0, const Integer y = 0) : x(x), y(y) {}Integer norm() const { return x * x + y * y; }Point& operator+=(const Point& p) {x += p.x; y += p.y;return *this;}Point& operator-=(const Point& p) {x -= p.x; y -= p.y;return *this;}Point& operator*=(const Integer k) {x *= k; y *= k;return *this;}Point& operator/=(const Integer k) {x /= k; y /= k;return *this;}std::strong_ordering operator<=>(const Point& p) const {const int x_sgn = sgn(p.x - x);if (x_sgn == 0) return 0 <=> sgn(p.y - y);return x_sgn == 1 ? std::strong_ordering::less :std::strong_ordering::greater;}Point operator+() const { return *this; }Point operator-() const { return Point(-x, -y); }Point operator+(const Point& p) const { return Point(*this) += p; }Point operator-(const Point& p) const { return Point(*this) -= p; }Point operator*(const Integer k) const { return Point(*this) *= k; }Point operator/(const Integer k) const { return Point(*this) /= k; }friend std::ostream& operator<<(std::ostream& os, const Point& p) {return os << '(' << p.x << ", " << p.y << ')';}friend std::istream& operator>>(std::istream& is, Point& p) {Integer x, y; is >> x >> y;p = Point(x, y);return is;}};struct Segment {Point s, t;explicit Segment(const Point& s = Point(0, 0), const Point& t = Point(0, 0)): s(s), t(t) {}};struct Line : Segment {using Segment::Segment;};struct Circle {Point p; Integer r;explicit Circle(const Point& p = Point(0, 0), const Integer r = 0): p(p), r(r) {}};Integer cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }Integer dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }int ccw(const Point& a, const Point& b, const Point& c) {const Point ab = b - a, ac = c - a;const int sign = sgn(cross(ab, ac));if (sign == 0) {if (sgn(dot(ab, ac)) == -1) return 2;if (sgn(ac.norm() - ab.norm()) == 1) return -2;}return sign;}Integer closest_pair(std::vector<Point> ps) {const int n = ps.size();assert(n >= 2);std::sort(ps.begin(), ps.end());const auto f = [&ps](auto f, const int left, const int right) -> Integer {const int mid = std::midpoint(left, right);Integer x_mid = ps[mid].x, d = std::numeric_limits<Integer>::max();if (left + 1 < mid) d = std::min(d, f(f, left, mid));if (mid + 1 < right) d = std::min(d, f(f, mid, right));std::inplace_merge(std::next(ps.begin(), left), std::next(ps.begin(), mid),std::next(ps.begin(), right),[](const Point& a, const Point& b) -> bool {return sgn(b.y - a.y) == 1;});std::vector<Point> tmp;for (int i = left; i < right; ++i) {if (sgn((ps[i].x - x_mid) * (ps[i].x - x_mid) - d) == 1) continue;for (int j = std::ssize(tmp) - 1; j >= 0; --j) {const Point v = ps[i] - tmp[j];if (sgn(v.y * v.y - d) == 1) break;d = std::min(d, v.norm());}tmp.emplace_back(ps[i]);}return d;};return f(f, 0, n);}bool is_parallel(const Segment& a, const Segment& b) {return sgn(cross(a.t - a.s, b.t - b.s)) == 0;}bool is_orthogonal(const Segment& a, const Segment& b) {return sgn(dot(a.t - a.s, b.t - b.s)) == 0;}int common_tangent_num(const Circle&, const Circle&);bool has_intersected(const Segment& a, const Point& b) {return ccw(a.s, a.t, b) == 0;}bool has_intersected(const Segment& a, const Segment& b) {return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) <= 0 &&ccw(b.s, b.t, a.s) * ccw(b.s, b.t, a.t) <= 0;}bool has_intersected(const Line& a, const Point& b) {const int c = ccw(a.s, a.t, b);return c != 1 && c != -1;}bool has_intersected(const Line& a, const Segment& b) {return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) != 1;}bool has_intersected(const Line& a, const Line& b) {return sgn(cross(a.t - a.s, b.t - b.s)) != 0 ||sgn(cross(a.t - a.s, b.s - a.s)) == 0;}bool has_intersected(const Circle& a, const Point& b) {return (a.p - b).norm() == a.r * a.r;}bool has_intersected(const Circle& a, const Circle& b) {const int num = common_tangent_num(a, b);return 1 <= num && num <= 3;}int common_tangent_num(const Circle& a, const Circle& b) {const Integer dist = (a.p - b.p).norm();int sign = sgn((a.r + b.r) * (a.r + b.r) - dist);if (sign == -1) return 4;if (sign == 0) return 3;sign = sgn((b.r - a.r) * (b.r - a.r) - dist);if (sign == -1) return 2;if (sign == 0) return 1;return 0;}using Polygon = std::vector<Point>;Integer area(Polygon a) {const int n = a.size();a.resize(n + 1);a.back() = a.front();Integer res = 0;for (int i = 0; i < n; ++i) {res += cross(a[i], a[i + 1]);}// return res / 2;return res;}int contains(Polygon a, const Point &b) {const int n = a.size();a.resize(n + 1);a.back() = a.front();bool is_in = false;for (int i = 0; i < n; ++i) {Point p = a[i] - b, q = a[i + 1] - b;if (sgn(q.y - p.y) == -1) std::swap(p, q);const int sign = sgn(cross(p, q));if (sign == 1 && sgn(p.y) != 1 && sgn(q.y) == 1) is_in = !is_in;if (sign == 0 && sgn(dot(p, q)) != 1) return 1;}return is_in ? 2 : 0;}bool is_convex(Polygon a) {const int n = a.size();a.resize(n + 2);a[n] = a[0];a[n + 1] = a[1];for (int i = 1; i <= n; ++i) {if (ccw(a[i - 1], a[i], a[i + 1]) == -1) return false;}return true;}template <bool IS_TIGHT = true>Polygon monotone_chain(std::vector<Point> ps) {const int n = ps.size();std::sort(ps.begin(), ps.end());Polygon convex_hull(n << 1);int idx = 0;for (int i = 0; i < n; convex_hull[idx++] = ps[i++]) {while (idx >= 2 &&sgn(cross(convex_hull[idx - 1] - convex_hull[idx - 2],ps[i] - convex_hull[idx - 1])) < IS_TIGHT) {--idx;}}for (int i = n - 2, border = idx + 1; i >= 0; convex_hull[idx++] = ps[i--]) {while (idx >= border &&sgn(cross(convex_hull[idx - 1] - convex_hull[idx - 2],ps[i] - convex_hull[idx - 1])) < IS_TIGHT) {--idx;}}convex_hull.resize(idx - 1);return convex_hull;}std::pair<Point, Point> rotating_calipers(Polygon a) {const int n = a.size();if (n <= 2) [[unlikely]] {assert(n == 2);return {a[0], a[1]};}a.resize(n + 1);a.back() = a.front();int high = 0, low = 0;for (int i = 1; i < n; ++i) {if (a[i].y > a[high].y) high = i;if (a[i].y < a[low].y) low = i;}Integer max_norm = (a[high] - a[low]).norm();int i = high, j = low, argmax_i = i, argmax_j = j;do {int* i_or_j = &(sgn(cross(a[i + 1] - a[i], a[j + 1] - a[j])) != -1 ? j : i);if (++(*i_or_j) == n) *i_or_j = 0;const Integer tmp = (a[j] - a[i]).norm();if (sgn(tmp - max_norm) == 1) {max_norm = tmp;argmax_i = i; argmax_j = j;}} while (i != high || j != low);return {a[argmax_i], a[argmax_j]};}} // namespace geometryint main() {using namespace geometry;const auto solve = [](const Point& x, const Point& y, const Point& z) -> int {return abs((x.x - z.x) * (y.y - z.y) - (y.x - z.x) * (x.y - z.y));};int n; cin >> n;vector<Point> p(n); REP(i, n) cin >> p[i];int ans = 0;REP(i, n) FOR(j, i + 1, n) {map<int, int> max_area;REP(k, n) {if (k != i && k != j) chmax(max_area[ccw(p[i], p[j], p[k])], solve(p[i], p[j], p[k]));}if (max_area.size() == 2) chmax(ans, max_area.begin()->second + max_area.rbegin()->second);}cout << ans << '\n';return 0;}