結果
| 問題 | No.2012 Largest Triangle |
| ユーザー |
 Carpenters-Cat
|
| 提出日時 | 2022-07-15 22:39:03 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 15,718 bytes |
| コンパイル時間 | 2,134 ms |
| コンパイル使用メモリ | 150,168 KB |
| 実行使用メモリ | 7,168 KB |
| 最終ジャッジ日時 | 2024-06-27 19:31:53 |
| 合計ジャッジ時間 | 13,116 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
ソースコード
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// def_class
using namespace std;
using ll = long long;
using Vi = vector<int>;
using VVi = vector<Vi>;
using Vl = vector<ll>;
using VVl = vector<Vl>;
using Pii = pair<int, int>;
using Vp = vector<Pii>;
using VVp = vector<Vp>;
using Pl = pair<ll, int>;
using Vpl = vector<Pl>;
using VVpl = vector<Vpl>;
using tup = tuple<ll, ll, int>;
using Vt = vector<tuple<int, int, int>>;
using Pll = pair<ll, ll>;
using Vc = vector<char>;
using VVc = vector<Vc>;
template <class U>
using PQmax = priority_queue<U>;
template <class U>
using PQmin = priority_queue<U, vector<U>, greater<U>>;
// func_def
//再帰で計算するトポロジカルソート
void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par);
void tprsort(int u, const VVpl& gr, Vi& tpr, Vi& par);
//キューで計算するトポロジカルソート
void tprsort(const VVi& gr, Vi& tpr);
ll mpow(ll x, ll n, ll m = 1e9 + 7);
ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m = 1e9 + 7);
ll gcd(ll a, ll b);
int LCA(const VVi& par, const Vi& depth, int a, int b);
Vi sccResolve(const VVi& gr);
void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s);
void dijkstra_prev(const VVi& gr, const VVl& cost, Vl& dist, Vi& prev, int s);
// ax + by = c
struct DLine {
ll a;
ll b;
ll c;
bool operator<(const DLine l) const;
};
DLine make_dline(ll x1, ll y1, ll x2, ll y2);
double calc_tilt(DLine l1);
bool is_upper(DLine l, ll x, ll y);
bool is_inside(DLine l, ll x, ll y);
class unionfind
{
private:
Vi par;
Vi siz;
public:
unionfind(int N);
unionfind();
int root(int v);
void merge(int a, int b);
bool same(int a, int b);
int size(int a);
};
class w_unionfind
{
private:
Vi par;
Vi siz;
Vi val;
public:
w_unionfind(int N);
w_unionfind();
int root(int v);
void merge(int a, int b, int z);
bool same(int a, int b);
int value(int a);
};
class BIT
{
private:
Vl bit;
int siz;
public:
BIT(int N);
BIT();
ll& get(int id);
void add(int id, ll a, ll m);
ll sum(int id, ll m);
};
class RMQ
{
private:
Vl val;
int siz;
ll e;
ll prod_sub(int l, int r, int a, int b, int id);
public:
RMQ(int N, ll e = (ll)1e18);
RMQ(Vl A, ll e = (ll)1e18);
RMQ(ll e = (ll)1e18);
ll& get(int id);
void set(int id, ll a);
void add(int id, ll a);
ll prod(int l, int r);
};
class Fraction
{
public:
ll mot;
ll son;
// a/b を生成
Fraction(ll a = 0, ll b = 1)
{
ll g = gcd(abs(a), abs(b));
if (b < 0) {
a *= -1;
b *= -1;
}
mot = b / g;
son = a / g;
}
Fraction(const Fraction& F) : mot(F.mot), son(F.son) {}
Fraction operator+(const Fraction A) const;
Fraction operator-(const Fraction A) const;
Fraction operator*(const Fraction A) const;
// Fraction operator/(const int& a);
Fraction operator/(const Fraction A) const;
Fraction operator=(const Fraction& A);
bool operator<(const Fraction A) const;
bool operator>(const Fraction A) const;
};
int main()
{
int N;
cin >> N;
vector<Pll> A(N);
for (auto& [a, b] : A) {
cin >> a >> b;
}
sort(A.begin(), A.end());
vector<Pll> U, D;
vector<Fraction> uf, df;
for (auto [a, b] : A) {
if (U.size() < 2) {
U.emplace_back(a, b);
} else {
while (U.size() >= 2) {
auto [a1, b1] = U.back();
auto [a2, b2] = U[U.size() - 2];
ll da1 = a - a1;
ll db1 = b - b1;
ll da2 = a2 - a1;
ll db2 = b2 - b1;
if (da1 * db2 <= db1 * da2) {
U.pop_back();
} else {
break;
}
}
U.emplace_back(a, b);
}
}
for (auto [a, b] : A) {
if (D.size() < 2) {
D.emplace_back(a, b);
} else {
while (D.size() >= 2) {
auto [a1, b1] = D.back();
auto [a2, b2] = D[D.size() - 2];
ll da1 = a - a1;
ll db1 = b - b1;
ll da2 = a2 - a1;
ll db2 = b2 - b1;
if (da1 * db2 >= db1 * da2) {
D.pop_back();
} else {
break;
}
}
D.emplace_back(a, b);
}
}
for (int i = 0; i < D.size() - 1; i++) {
auto [p1, p2] = D[i];
auto [q1, q2] = D[i + 1];
df.push_back(Fraction{q2 - p2, q1 - p1});
}
for (int i = 0; i < U.size() - 1; i++) {
auto [p1, p2] = U[i];
auto [q1, q2] = U[i + 1];
uf.push_back(Fraction{q2 - p2, q1 - p1});
}
for (int i = 0; i < uf.size() - 1; i ++) {
assert(uf[i] > uf[i + 1]);
}
for (int i = 0; i < df.size() - 1; i ++) {
assert(df[i] < df[i + 1]);
}
ll ans = 0;
for (auto [a, b] : A) {
Fraction F{-b, a};
int ma = D.size();
int mi = 0;
while (ma - mi > 1) {
int mu = (ma + mi) / 2;
if (df[mu - 1] < F) {
mi = mu;
} else {
ma = mu;
}
}
auto [x, y] = D[mi];
ans = max(ans, abs(a * y - b * x));
ma = U.size();
mi = 0;
while (ma - mi > 1) {
int mu = (ma + mi) / 2;
if (uf[mu - 1] > F) {
mi = mu;
} else {
ma = mu;
}
}
auto [x1, y1] = U[mi];
ans = max(ans, abs(a * y1 - b * x1));
}
cout << ans << endl;
}
// Library
// pair<ll, int> 用
void tprsort(int u, const VVpl& gr, Vi& tpr, Vi& par)
{
// idx[u] = tpr.size();
/*for (int v : gr[u]) {
if (par[v] == u || par[v] == -1) {
par[v] = u;
tprsort(v, gr, tpr, par);
}
}
tpr.push_back(u);*/
stack<int> st;
st.push(u);
bool vis[2000020];
for (int i = 0; i <= gr.size(); i++) {
vis[i] = false;
}
while (!st.empty()) {
int v = st.top();
if (!vis[v]) {
vis[v] = true;
for (auto [x, p] : gr[v]) {
if (par[p] == -1) {
par[p] = v;
st.push(p);
}
}
} else {
tpr.push_back(v);
st.pop();
}
}
}
//再帰型
void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par)
{
// idx[u] = tpr.size();
/*for (int v : gr[u]) {
if (par[v] == u || par[v] == -1) {
par[v] = u;
tprsort(v, gr, tpr, par);
}
}
tpr.push_back(u);*/
stack<int> st;
st.push(u);
bool vis[2000020];
for (int i = 0; i <= gr.size(); i++) {
vis[i] = false;
}
while (!st.empty()) {
int v = st.top();
if (!vis[v]) {
vis[v] = true;
for (int p : gr[v]) {
if (par[p] == -1) {
par[p] = v;
st.push(p);
}
}
} else {
tpr.push_back(v);
st.pop();
}
}
}
Vi sccResolve(const VVi& gr)
{
int N = gr.size();
Vi tpr;
Vi par(N, -1);
for (int i = 0; i < N; i++) {
if (par[i] == -1) {
tprsort(i, gr, tpr, par);
}
}
Vi ret(N, -1);
int now = 0;
for (int i = N - 1; i >= 0; i--) {
int u = tpr[i];
if (ret[u] != -1) {
continue;
}
ret[u] = now;
stack<int> st;
st.push(u);
while (!st.empty()) {
int v = st.top();
st.pop();
for (int p : gr[v]) {
if (ret[p] == -1) {
st.push(p);
ret[p] = now;
}
}
}
now++;
}
return ret;
}
ll gcd(ll a, ll b)
{
while (b) {
a %= b;
swap(a, b);
}
return a;
}
ll mpow(ll x, ll n, ll m)
{
ll ret = 1;
while (n) {
if (n % 2) {
ret *= x;
ret %= m;
}
x = (x * x) % m;
n /= 2;
}
return ret;
}
ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m)
{
if (n < 0 || r < 0 || n < r) {
return 0;
}
ll ret = kai[n];
ret *= fkai[r];
ret %= m;
ret *= fkai[n - r];
ret %= m;
return ret;
}
int LCA(const VVi& par, const Vi& depth, int a, int b)
{
if (depth[a] < depth[b]) {
swap(a, b);
}
int dis = depth[a] - depth[b];
for (int i = 19; i >= 0; i--) {
if ((dis >> i) & 1) {
a = par[i][a];
}
}
if (a == b) {
return a;
}
for (int i = 19; i >= 0; i--) {
if (par[i][a] != par[i][b]) {
a = par[i][a];
b = par[i][b];
}
}
return par[0][a];
}
void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s)
{
ll INF = (ll)1e18;
dist.assign(gr.size(), INF);
dist[s] = 0;
PQmin<Pl> pque;
pque.push(make_pair(0, s));
while (!pque.empty()) {
auto [L, u] = pque.top();
pque.pop();
while (L != dist[u] && !pque.empty()) {
tie(L, u) = pque.top();
pque.pop();
}
for (int i = 0; i < gr[u].size(); i++) {
int v = gr[u][i];
ll c = cost[u][i];
if (dist[v] > c + L) {
dist[v] = c + L;
pque.push(make_pair(dist[v], v));
}
}
}
return;
}
void dijkstra_prev(const VVi& gr, const VVl& cost, Vl& dist, Vi& prev, int s)
{
ll INF = (ll)1e18;
dist.assign(gr.size(), INF);
dist[s] = 0;
PQmin<Pl> pque;
pque.push(make_pair(0, s));
while (!pque.empty()) {
auto [L, u] = pque.top();
pque.pop();
while (L != dist[u] && !pque.empty()) {
tie(L, u) = pque.top();
pque.pop();
}
for (int i = 0; i < gr[u].size(); i++) {
int v = gr[u][i];
ll c = cost[u][i];
if (dist[v] > c + L) {
dist[v] = c + L;
prev[v] = u;
pque.push(make_pair(dist[v], v));
}
}
}
return;
}
DLine make_dline(ll x1, ll y1, ll x2, ll y2)
{
ll dx = x1 - x2;
ll dy = y2 - y1;
if (dy < 0) {
dx *= -1;
dy *= -1;
}
if (dy == 0) {
dx = abs(dx);
}
ll g = gcd(dy, abs(dx));
dx /= g;
dy /= g;
ll c = dx * y1 + dy * x1;
return DLine{dy, dx, c};
}
double calc_tilt(DLine l)
{
return atan2(l.a, l.b);
}
bool is_upper(DLine l, ll x, ll y)
{
return x * l.a + y * l.b > l.c;
}
bool is_inside(DLine l, ll x, ll y)
{
return x * l.a + y * l.b == l.c;
}
unionfind::unionfind(int N)
{
par.resize(N);
siz.assign(N, 1);
for (int i = 0; i < N; i++) {
par[i] = i;
}
}
unionfind::unionfind()
{
par.resize(100010);
siz.assign(100010, 1);
for (int i = 0; i <= 100010; i++) {
par[i] = i;
}
}
int unionfind::root(int v)
{
if (v == par[v]) {
return v;
}
return par[v] = root(par[v]);
}
void unionfind::merge(int a, int b)
{
a = root(a);
b = root(b);
if (a == b) {
return;
}
if (siz[a] < siz[b]) {
int t = a;
a = b;
b = t;
}
par[b] = a;
siz[a] += siz[b];
}
bool unionfind::same(int a, int b)
{
a = root(a);
b = root(b);
return a == b;
}
int unionfind::size(int a)
{
return siz[this->root(a)];
}
w_unionfind::w_unionfind(int N)
{
par.resize(N);
siz.assign(N, 1);
val.assign(N, 0);
for (int i = 0; i < N; i++) {
par[i] = i;
}
}
w_unionfind::w_unionfind()
{
par.resize(100010);
siz.assign(100010, 1);
val.assign(100010, 0);
for (int i = 0; i <= 100010; i++) {
par[i] = i;
}
}
int w_unionfind::root(int v)
{
if (v == par[v]) {
return v;
}
int p = root(par[v]);
val[v] += val[par[v]];
par[v] = p;
return p;
}
void w_unionfind::merge(int a, int b, int z)
{
z -= this->value(b);
z += this->value(a);
a = root(a);
b = root(b);
if (a == b) {
return;
}
if (siz[a] < siz[b]) {
int t = a;
a = b;
b = t;
z *= -1;
}
par[b] = a;
siz[a] += siz[b];
val[b] += z;
}
bool w_unionfind::same(int a, int b)
{
a = root(a);
b = root(b);
return a == b;
}
int w_unionfind::value(int a)
{
root(a);
return val[a];
}
BIT::BIT(int N)
{
siz = N;
bit.assign(N + 1, 0);
}
BIT::BIT()
{
siz = 0;
}
ll& BIT::get(int id)
{
return bit[id];
}
void BIT::add(int id, ll a, ll m)
{
while (id <= siz) {
bit[id] += a;
bit[id] %= m;
id += (id & (-id));
}
}
ll BIT::sum(int id, ll m)
{
ll ret = 0;
while (id) {
ret += bit[id];
ret %= m;
id -= (id & (-id));
}
return ret;
}
RMQ::RMQ(int N, ll e)
{
siz = 1;
this->e = e;
while (siz < N) {
siz *= 2;
}
val.assign(siz * 2, e);
}
RMQ::RMQ(Vl A, ll e)
{
siz = 1;
this->e = e;
while (siz < A.size()) {
siz *= 2;
}
val.assign(siz * 2, e);
for (int i = 0; i < A.size(); i++) {
val[i + siz - 1] = A[i];
}
for (int i = siz - 2; i >= 0; i--) {
int l = i * 2 + 1;
int r = i * 2 + 2;
val[i] = min(val[l], val[r]);
}
}
RMQ::RMQ(ll e)
{
siz = (1 << 20);
this->e = e;
val.assign(siz * 2, e);
}
ll& RMQ::get(int id)
{
return val[id + siz - 1];
}
void RMQ::set(int id, ll a)
{
id += siz - 1;
val[id] = a;
while (id > 0) {
id = (id - 1) / 2;
int l = id * 2 + 1;
int r = id * 2 + 2;
ll v = min(val[l], val[r]);
/*if (val[id] == v) {
break;
}*/
val[id] = v;
}
}
void RMQ::add(int id, ll a)
{
ll n = a + val[id + siz - 1];
this->set(id, n);
}
ll RMQ::prod_sub(int l, int r, int a, int b, int id)
{
if (b <= l || r <= a) {
return this->e;
}
if (l <= a && b <= r) {
return val[id];
}
return min(this->prod_sub(l, r, a, (a + b) / 2, id * 2 + 1),
this->prod_sub(l, r, (a + b) / 2, b, id * 2 + 2));
}
ll RMQ::prod(int l, int r)
{
return prod_sub(l, r, 0, siz, 0);
}
Fraction Fraction::operator+(const Fraction A) const
{
return Fraction{this->son * A.mot + A.son * this->mot, this->mot * A.mot};
}
Fraction Fraction::operator-(const Fraction A) const
{
return Fraction{this->son * A.mot - A.son * this->mot, this->mot * A.mot};
}
Fraction Fraction::operator*(const Fraction A) const
{
return Fraction{this->son * A.son, this->mot * A.mot};
}
// Fraction Fraction::operator/(const int& a)
// {
// return *this / (ll)a;
// }
Fraction Fraction::operator/(const Fraction A) const
{
return Fraction{this->son * A.mot, this->mot * A.son};
}
Fraction Fraction::operator=(const Fraction& A)
{
this->mot = A.mot;
this->son = A.son;
return *this;
}
bool Fraction::operator<(const Fraction A) const
{
return this->son * A.mot < this->mot * A.son;
}
bool Fraction::operator>(const Fraction A) const
{
return A < *this;
}
bool DLine::operator<(const DLine l) const
{
if (a == l.a && b == l.b) {
return c < l.c;
}
return Fraction{a, -b} < Fraction{l.a, -l.b};
}