結果
| 問題 | No.2012 Largest Triangle |
| ユーザー |
 satashun
|
| 提出日時 | 2022-07-15 22:49:21 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 14,094 bytes |
| コンパイル時間 | 2,990 ms |
| コンパイル使用メモリ | 230,548 KB |
| 実行使用メモリ | 28,232 KB |
| 最終ジャッジ日時 | 2023-09-10 05:48:39 |
| 合計ジャッジ時間 | 17,518 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
11,480 KB |
| testcase_01 | AC | 2 ms
4,384 KB |
| testcase_02 | AC | 2 ms
4,380 KB |
| testcase_03 | AC | 2 ms
4,380 KB |
| testcase_04 | AC | 2 ms
4,384 KB |
| testcase_05 | AC | 2 ms
4,380 KB |
| testcase_06 | AC | 2 ms
4,380 KB |
| testcase_07 | AC | 1 ms
4,384 KB |
| testcase_08 | AC | 2 ms
4,380 KB |
| testcase_09 | AC | 2 ms
4,380 KB |
| testcase_10 | AC | 2 ms
4,380 KB |
| testcase_11 | AC | 2 ms
4,384 KB |
| testcase_12 | AC | 2 ms
4,384 KB |
| testcase_13 | AC | 2 ms
4,380 KB |
| testcase_14 | AC | 2 ms
4,384 KB |
| testcase_15 | AC | 2 ms
4,384 KB |
| testcase_16 | AC | 166 ms
28,104 KB |
| testcase_17 | AC | 166 ms
28,112 KB |
| testcase_18 | AC | 166 ms
28,176 KB |
| testcase_19 | AC | 164 ms
28,048 KB |
| testcase_20 | AC | 166 ms
28,052 KB |
| testcase_21 | AC | 166 ms
28,144 KB |
| testcase_22 | AC | 165 ms
28,140 KB |
| testcase_23 | AC | 166 ms
28,216 KB |
| testcase_24 | AC | 167 ms
28,064 KB |
| testcase_25 | AC | 166 ms
28,108 KB |
| testcase_26 | AC | 1,121 ms
28,148 KB |
| testcase_27 | AC | 925 ms
28,128 KB |
| testcase_28 | AC | 1,091 ms
28,100 KB |
| testcase_29 | AC | 1,061 ms
28,028 KB |
| testcase_30 | AC | 1,090 ms
28,136 KB |
| testcase_31 | AC | 166 ms
28,064 KB |
| testcase_32 | AC | 167 ms
28,100 KB |
| testcase_33 | AC | 167 ms
28,232 KB |
| testcase_34 | AC | 170 ms
28,116 KB |
| testcase_35 | AC | 167 ms
28,040 KB |
| testcase_36 | AC | 6 ms
4,384 KB |
| testcase_37 | AC | 6 ms
4,380 KB |
| testcase_38 | AC | 7 ms
4,384 KB |
| testcase_39 | AC | 6 ms
4,380 KB |
| testcase_40 | AC | 6 ms
4,384 KB |
| testcase_41 | TLE | - |
ソースコード
#pragma region satashun
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
template <class T>
V<T> make_vec(size_t a) {
return V<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
return V<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T, class U>
void chmin(T &t, const U &u) {
if (t > u) t = u;
}
template <class T, class U>
void chmax(T &t, const U &u) {
if (t < u) t = u;
}
template <class T>
void mkuni(vector<T> &v) {
sort(ALL(v));
v.erase(unique(ALL(v)), end(v));
}
template <class T>
vector<int> sort_by(const vector<T> &v, bool increasing = true) {
vector<int> res(v.size());
iota(res.begin(), res.end(), 0);
if (increasing) {
stable_sort(res.begin(), res.end(),
[&](int i, int j) { return v[i] < v[j]; });
} else {
stable_sort(res.begin(), res.end(),
[&](int i, int j) { return v[i] > v[j]; });
}
return res;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << "(" << p.first << "," << p.second << ")";
return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
for (auto &x : v) {
is >> x;
}
return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << "{";
rep(i, v.size()) {
if (i) os << ",";
os << v[i];
}
os << "}";
return os;
}
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) \
cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
template <class T>
void scan(vector<T> &v, T offset = T(0)) {
for (auto &x : v) {
cin >> x;
x += offset;
}
}
// suc : 1 = newline, 2 = space
template <class T>
void print(T x, int suc = 1) {
cout << x;
if (suc == 1)
cout << "\n";
else if (suc == 2)
cout << " ";
}
template <class T>
void print(const vector<T> &v, int suc = 1) {
for (int i = 0; i < v.size(); ++i)
print(v[i], i == int(v.size()) - 1 ? suc : 2);
}
template <class T>
void show(T x) {
print(x, 1);
}
template <typename Head, typename... Tail>
void show(Head H, Tail... T) {
print(H, 2);
show(T...);
}
struct prepare_io {
prepare_io() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
}
} prep_io;
#pragma endregion satashun
// intersectSP modified on 2018/7/5
namespace geom {
#define X real()
#define Y imag()
#define at(i) ((*this)[i])
#define EPS (1e-9)
#define PI (3.1415926535897932384626)
using R = long double;
using P = complex<R>;
inline int sgn(R a, R b = 0) { return a < b - EPS ? -1 : a > b + EPS ? 1 : 0; }
inline bool near(P a, P b) { return !sgn(abs(a - b)); }
inline R norm(const P &p) { return p.X * p.X + p.Y * p.Y; }
inline R dot(const P &a, const P &b) { return real(a * conj(b)); }
inline R cross(const P &a, const P &b) { return imag(conj(a) * b); }
inline R sr(R a) { return sqrt(max(a, (R)0)); }
inline P unit(const P &p) { return p / abs(p); }
inline P proj(const P &s, const P &t) { return t * dot(s, t) / norm(t); }
struct L : public vector<P> { // line
L() {}
L(const P &a, const P &b) {
this->push_back(a);
this->push_back(b);
}
P dir() const { return at(1) - at(0); }
};
struct G : public vector<P> {
G(int sz = 0) : vector(sz) {}
L edge(int i) const { return L(at(i), at(i + 1 == size() ? 0 : i + 1)); }
};
//(a->b->c)
int ccw(P a, P b, P c) {
b -= a;
c -= a;
R cr = cross(b, c);
if (sgn(cr) > 0) return 1; // counter clockwise
if (sgn(cr) < 0) return -1; // clockwise
if (sgn(dot(b, c)) < 0) return 2; // c--a--b on line
if (sgn(norm(b), norm(c)) < 0) return -2; // a--b--c on line
return 0;
}
// L..line, S..segment, P..point
bool intersectLL(const L &l, const L &m) {
return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // non-parallel
abs(cross(l[1] - l[0], m[0] - l[0])) < EPS; // same line
}
bool intersectLS(const L &l, const L &s) {
return cross(l[1] - l[0], s[0] - l[0]) * // s[0] is left of l
cross(l[1] - l[0], s[1] - l[0]) <
EPS; // s[1] is right of l
}
bool intersectLP(const L &l, const P &p) {
return abs(cross(l[1] - p, l[0] - p)) < EPS;
}
bool intersectSS(const L &s, const L &t) {
return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}
bool intersectSP(const L &s, const P &p) { return !ccw(s[0], s[1], p); }
inline P proj(const P &s, const L &t) {
return t[0] + proj(s - t[0], t[1] - t[0]);
}
P projection(const L &l, const P &p) {
R t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
return l[0] + t * (l[0] - l[1]);
}
P reflection(const L &l, const P &p) {
return p + (projection(l, p) - p) * (R)2;
}
R distanceLP(const L &l, const P &p) { return abs(p - projection(l, p)); }
R distanceLL(const L &l, const L &m) {
return intersectLL(l, m) ? 0 : distanceLP(l, m[0]);
}
R distanceLS(const L &l, const L &s) {
if (intersectLS(l, s)) return 0;
return min(distanceLP(l, s[0]), distanceLP(l, s[1]));
}
R distanceSP(const L &s, const P &p) {
const P r = projection(s, p);
if (intersectSP(s, r)) return abs(r - p);
return min(abs(s[0] - p), abs(s[1] - p));
}
R distanceSS(const L &s, const L &t) {
if (intersectSS(s, t)) return 0;
return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}
P crosspoint(const L &l, const L &m) {
R A = cross(l[1] - l[0], m[1] - m[0]);
R B = cross(l[1] - l[0], l[1] - m[0]);
if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
return m[0] + B / A * (m[1] - m[0]);
}
struct C {
P c;
R r;
};
pair<P, P> crosspoint(C a, C b) {
R d = abs(a.c - b.c);
R l = ((a.r * a.r - b.r * b.r) / d + d) / 2.0;
R h = sqrt(a.r * a.r - l * l);
P e = a.c + (b.c - a.c) * l / d;
P p = (b.c - a.c) * h / d * P(0, -1);
return make_pair(e + p, e - p);
}
pair<P, P> crosspoint(C c, L l) {
P p = projection(l, c.c);
R d = abs(p - c.c);
P ve = unit(l.dir());
R w = sr(c.r * c.r - d * d);
return mp(p - w * ve, p + w * ve);
}
R area(P a, P b, P c) { return imag(conj(b - a) * (c - a)) * 0.5; }
#define curr(P, i) P[i]
#define next(P, i) P[(i + 1) % P.size()]
R poly_area(const G &vec) {
R ret = 0.0;
rep(i, vec.size()) ret += cross(curr(vec, i), next(vec, i));
return fabs(ret) / (R)2;
}
// center of mass
P center(const G &vec) {
R ar = 0;
P c(0, 0);
rep(i, vec.size()) {
P a = curr(vec, i), b = next(vec, i);
R t = a.X * b.Y - b.X * a.Y;
ar += t;
c += (a + b) * t;
}
c /= 3 * ar;
return c;
}
// polygon,point
enum { OUT, ON, IN };
int contains(const G &vec, const P &p) {
bool in = false;
for (int i = 0; i < vec.size(); ++i) {
P a = curr(vec, i) - p, b = next(vec, i) - p;
if (imag(a) > imag(b)) swap(a, b);
if (imag(a) <= 0 && 0 < imag(b))
if (cross(a, b) < 0) in = !in;
if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
}
return in ? IN : OUT;
}
/* 精密
enum { TRUE = 1, FALSE = 0, BORDER = -1 };
int contains(const G& vec, const P &p) {
R sum = .0;
rep(i, vec.size()) {
L l(curr(vec, i), next(vec, i));
if (intersectSP(l, p)) return BORDER;
sum += arg((curr(vec, i) - p) / (next(vec, i) - p));
}
return !!sgn(sum);
}
*/
bool containSG(const L &s, const G &vec) {
vector<P> p;
p.push_back(s[0]);
p.push_back(s[1]);
for (int i = 0; i < vec.size(); ++i) {
L e(vec[i], vec[(i + 1) % vec.size()]);
if (abs(cross(e[1] - e[0], s[1] - s[0])) > EPS) {
if (intersectSS(e, s)) p.push_back(crosspoint(e, s));
}
if (intersectSP(s, vec[i])) p.push_back(vec[i]);
}
sort(ALL(p));
for (int i = 0; i < (int)p.size() - 1; ++i) {
P pt = (p[i] + p[i + 1]) / R(2);
if (contains(vec, pt) == OUT) return false;
}
return true;
}
G convex_cut(const G &Pl, const L &l) {
G Q;
for (int i = 0; i < Pl.size(); ++i) {
P A = curr(Pl, i), B = next(Pl, i);
if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
if (ccw(l[0], l[1], A) * ccw(l[0], l[1], B) < 0)
Q.push_back(crosspoint(L(A, B), l));
}
return Q;
}
G convex_hull(G ps) {
int n = ps.size(), k = 0;
sort(ALL(ps), [&](const P &a, const P &b) {
return sgn(a.X - b.X) ? a.X < b.X : a.Y < b.Y;
});
G ch(2 * n);
for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) // upper-hull
while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
ch.resize(k - 1);
return ch;
}
struct DualGraph {
struct DEdge {
int u, v, f, l;
R a;
DEdge(int u, int v, R a) : u(u), v(v), f(0), l(0) {
while (PI < a) a -= 2 * PI;
while (a < -PI) a += 2 * PI;
this->a = a;
}
bool operator==(const DEdge &opp) const { return v == opp.v; }
bool operator<(const DEdge &opp) const { return a > opp.a; }
bool operator<(const R &opp) const { return a > opp; }
};
int n;
vector<P> p;
vector<vector<DEdge>> g;
DualGraph(const vector<P> &p) : p(p), g(p.size()), n(p.size()) {}
void add_edge(int s, int t) {
R a = arg(p[t] - p[s]);
g[s].emplace_back(s, t, a);
g[t].emplace_back(t, s, a + PI);
}
vector<G> poly;
void add_polygon(int s, int t, R a) {
auto e = lower_bound(ALL(g[s]), a - EPS);
if (e == g[s].end()) e = g[s].begin();
if (e->f) return;
e->f = 1;
e->l = t;
poly[t].push_back(p[s]);
add_polygon(e->v, t, e->a > 0 ? e->a - PI : e->a + PI);
}
vector<G> &dual() {
rep(i, n) {
sort(ALL(g[i]));
g[i].erase(unique(ALL(g[i])), g[i].end());
}
int s = min_element(ALL(p)) - p.begin();
poly.emplace_back();
add_polygon(s, poly.size() - 1, -PI * (R).5);
rep(i, n) rep(j, g[i].size()) if (!g[i][j].f) {
poly.emplace_back();
add_polygon(i, poly.size() - 1, g[i][j].a + 2. * EPS);
}
return poly;
}
};
template <class T>
void merge(vector<T> &s) {
rep(i, s.size()) if (s[i][1] < s[i][0]) swap(s[i][0], s[i][1]);
sort(ALL(s));
rep(i, s.size())
rep(j, i) if (!sgn(cross(s[i][1] - s[i][0], s[j][1] - s[j][0])) &&
intersectSS(s[i], s[j])) {
s[j][1] = max(s[i][1], s[j][1]);
s.erase(s.begin() + i--);
break;
}
}
struct Arrangement {
struct AEdge {
int u, v, t;
R cost;
AEdge() {}
AEdge(int u = 0, int v = 0, int t = 0, R cost = 0)
: u(u), v(v), t(t), cost(cost) {}
};
typedef vector<vector<AEdge>> AGraph;
vector<P> p;
AGraph g;
Arrangement() {}
Arrangement(vector<L> &seg) {
merge(seg);
int m = seg.size();
rep(i, m) {
p.push_back(seg[i][0]);
p.push_back(seg[i][1]);
rep(j, i) if (sgn(cross(seg[i][1] - seg[i][0],
seg[j][1] - seg[j][0]) &&
intersectSS(seg[i], seg[j])))
p.push_back(crosspoint(seg[i], seg[j]));
}
sort(ALL(p));
p.erase(unique(ALL(p)), p.end());
int n = p.size();
g.resize(n);
rep(i, m) {
L &s = seg[i];
vector<pair<R, int>> ps;
rep(j, n) if (intersectSP(s, p[j]))
ps.emplace_back(norm(p[j] - s[0]), j);
sort(ALL(ps));
rep(j, (int)ps.size() - 1) {
const int u = ps[j].second;
const int v = ps[j + 1].second;
g[u].emplace_back(u, v, 0, abs(p[u] - p[v]));
g[v].emplace_back(v, u, 0, abs(p[u] - p[v]));
}
}
}
};
} // namespace geom
using namespace geom;
namespace std {
bool operator<(const P &a, const P &b) {
return sgn(a.X - b.X) ? a.X < b.X : a.Y < b.Y;
}
istream &operator>>(istream &is, P &p) {
R x, y;
is >> x >> y;
p = P(x, y);
return is;
}
} // namespace std
void slv() {
int N;
cin >> N;
ll ans = 0;
G pl(N);
cin >> pl;
auto hull = convex_hull(pl);
V<P> vec;
for (auto p : hull) {
for (auto q : hull) {
ll ar = abs(cross(p, q));
chmax(ans, ar);
}
}
show(ans);
}
int main() {
int cases = 1;
// cin >> cases;
rep(i, cases) slv();
return 0;
}