結果
問題 | No.2012 Largest Triangle |
ユーザー |
![]() |
提出日時 | 2023-02-12 17:49:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 9,362 bytes |
コンパイル時間 | 3,293 ms |
コンパイル使用メモリ | 220,632 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2023-09-23 06:23:28 |
合計ジャッジ時間 | 34,889 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 1,111 ms
6,144 KB |
testcase_20 | WA | - |
testcase_21 | AC | 1,079 ms
6,152 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 1,105 ms
6,208 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | AC | 10 ms
4,376 KB |
testcase_39 | AC | 10 ms
4,384 KB |
testcase_40 | AC | 10 ms
4,376 KB |
testcase_41 | WA | - |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/2012" #include <bits/stdc++.h> using namespace std; template<typename T> struct Line{ T a,b; Line()=default; Line(T a,T b):a(a),b(b){} Line(pair<T,T> l):a(l.first),b(l.second){} Line(T c):a(0),b(c){} T operator()(const T x)const{ return a*x+b; } Line operator()(const Line&l)const{ return Line(a*l.a, a*l.b+b); } bool operator==(const Line&l)const{ return a==l.a and b==l.b; } bool operator!=(const Line&l)const{ return !(*this == l); } bool operator<(const Line&l)const{ return (a==l.a ? a<l.a : b<l.b); } Line&operator+=(const Line&l){ a+=l.a; b+=l.b; return *this; } Line operator+(const Line&l)const{return Line(*this) += l; } Line&operator-=(const Line&l){ a-=l.a; b-=l.b; return *this; } Line operator-(const Line&l)const{return Line(*this) -= l; } Line operator-()const{ return Line(-a,-b); } Line&operator+=(const T&c){ b+=c; return *this; } Line operator+(const T&c)const{ return Line(*this) += c; } Line&operator-=(const T&c){ b-=c; return *this; } Line operator-(const T&c)const{ return Line(*this) -= c; } Line&operator*=(const T&c){ a*=c; b*=c; return *this; } Line operator*(const T&c)const{ return Line(*this) *= c; } Line&operator/=(const T&c){ a/=c; b/=c; return *this; } Line operator/(const T&c)const{ return Line(*this) /= c; } Line inv()const{ assert(a!=0); return Line(T(1)/a, -b/a); } friend istream&operator>>(istream&is,Line&l){ is>>l.a>>l.b; return is; } friend ostream&operator<<(ostream&os,const Line&l){ os<<l.a<<"x+"<<l.b; return os; } }; namespace convex_hull_trick{ enum Objective{ MINIMIZE = +1, MAXIMIZE = -1, }; template<typename T,Objective OBJ> class ConvexHullTrick:deque<Line<T>>{ using L=Line<T>; using deque<L>::back; using deque<L>::front; using deque<L>::push_back; using deque<L>::push_front; using deque<L>::pop_back; using deque<L>::pop_front; using deque<L>::at; static bool check(const L&l1,const L&l2,const L&l3){ return (l2.b-l1.b)*(l2.a-l3.a) >= (l3.b-l2.b)*(l1.a-l2.a); } void internal_push_back(const L&l){ if(size()){ if(back().a == l.a){ if(back().b <= l.b)return; else pop_back(); } while(size() >= 2){ L l1 = at(size()-2), l2 = back(); if(check(l1,l2,l))pop_back(); else break; } } push_back(l); } void internal_push_front(const L&l){ if(size()){ if(front().a == l.a){ if(front().b >= l.b)return; else pop_front(); } while(size() >= 2){ L l2 = at(0), l3 = at(1); if(check(l,l2,l3))pop_front(); else break; } } push_front(l); } public: using value_type = L; using deque<L>::size; ConvexHullTrick()=default; ConvexHullTrick(vector<L> lines){ if(OBJ==-1)for(auto&l:lines)l=-l; sort(lines.begin(),lines.end()); for(const auto&[a,b]:lines)internal_push_back(a,b); } void add(L l){ if(OBJ==-1)l=-l; if(!size() or back().a >= l.a)internal_push_back(l); else if(l.a >= front().a)internal_push_front(l); else assert(false); } void add(T a,T b){ add(L(a,b)); } T query(T x)const{ assert(size()); int l=-1,r=size()-1; while(r-l>1){ int m=(l+r)>>1; (at(m)(x)>=at(m+1)(x) ? l : r)=m; } return at(r)(x)*OBJ; } T query_monotone_inc(T x){ assert(size()); while(size()>=2 and at(0)(x)>=at(1)(x)) pop_front(); return at(0)(x)*OBJ; } T query_monotone_dec(T x){ assert(size()); while(size()>=2 and at(size()-2)(x)<=back()(x)) pop_back(); return back()(x)*OBJ; } vector<T> query(const vector<T>&xs){ int n=xs.size(); vector<int> idx(n); iota(idx.begin(),idx.end(),0); sort(idx.begin(),idx.end(),[&](int i,int j){ return xs[i]<xs[j]; }); vector<T> ans(n); for(int id:idx)ans[id]=query_monotone_inc(xs[id]); return ans; } }; } template<typename T> using MinConvexHullTrick = convex_hull_trick::ConvexHullTrick<T,convex_hull_trick::Objective::MINIMIZE>; template<typename T> using MaxConvexHullTrick = convex_hull_trick::ConvexHullTrick<T,convex_hull_trick::Objective::MAXIMIZE>; template<typename T> struct XY{ T x,y; XY()=default; XY(T x,T y):x(x),y(y){} XY operator+()const{ return *this; } XY operator-()const{ return XY(-x,-y); } XY& operator++(){ x++;y++;return *this; } XY& operator--(){ x--;y--;return *this; } XY& operator++(int){ XY a=*this; ++*this; return a; } XY& operator--(int){ XY a=*this; --*this; return a; } XY& operator+=(const XY& v){ x+=v.x; y+=v.y; return *this; } XY& operator-=(const XY& v){ x-=v.x; y-=v.y; return *this; } XY& operator*=(const T& a){ x*=a; y*=a; return *this; } XY& operator/=(const T& a){ x/=a; y/=a; return *this; } friend XY operator+(const XY& u,const XY& v){ return XY(u)+=v; } friend XY operator-(const XY& u,const XY& v){ return XY(u)-=v; } friend XY operator*(const XY&u,const T& a){ return XY(u)*=a; } friend XY operator*(const T& a,const XY&u){ return XY(u)*=a; } friend XY operator/(const XY&u,const T& a){ return XY(u)/=a; } bool operator<(const XY&v)const{ return x!=v.x ? x<v.x : y<v.y; } bool operator>(const XY&v)const{ return x!=v.x ? x>v.x : y>v.y; } bool operator==(const XY&v)const{ return x==v.x and y==v.y; } bool operator!=(const XY&v)const{ return !(*this==v); } double arg()const{ return atan2(y,x); } friend T dot(const XY&u,const XY& v){ return u.x*v.x + u.y*v.y; } T norm(){ return dot(*this,*this); } T abs(){ return sqrt(norm()); } friend istream&operator>>(istream&is,XY&v){ is>>v.x>>v.y; return is; } friend ostream&operator<<(ostream&os,const XY&v){ os<<v.x<<" "<<v.y; return os;} }; template<typename T> struct Fraction{ T num,den; Fraction(T n=0,T d=1):num(n),den(d){ assert(den!=0); if(den<0)num=-num,den=-den; T g=gcd(abs(num),abs(den)); num/=g; den/=g; } Fraction operator+(const Fraction& b)const{ return Fraction( num*b.den + den*b.num, den*b.den ); } Fraction operator-(const Fraction& b)const{ return Fraction( num*b.den - den*b.num, den*b.den ); } Fraction operator*(const Fraction& b)const{ return Fraction( num*b.num, den*b.den ); } Fraction operator/(const Fraction& b)const{ return Fraction( num*b.den, den*b.num ); } Fraction& operator+=(const Fraction& b){ return *this = (*this) + b; } Fraction& operator-=(const Fraction& b){ return *this = (*this) - b; } Fraction& operator*=(const Fraction& b){ return *this = (*this) * b; } Fraction& operator/=(const Fraction& b){ return *this = (*this) / b; } Fraction operator+(const T&c)const{ return (*this)+Fraction(c,1); } Fraction operator-(const T&c)const{ return (*this)-Fraction(c,1); } Fraction operator*(const T&c)const{ return (*this)*Fraction(c,1); } Fraction operator/(const T&c)const{ return (*this)/Fraction(c,1); } friend Fraction operator+(const T&c, Fraction b){ return Fraction(c,1)+b; } friend Fraction operator-(const T&c, Fraction b){ return Fraction(c,1)-b; } friend Fraction operator*(const T&c, Fraction b){ return Fraction(c,1)*b; } friend Fraction operator/(const T&c, Fraction b){ return Fraction(c,1)/b; } Fraction& operator+=(const T&c){ return *this = (*this)+c; } Fraction& operator-=(const T&c){ return *this = (*this)-c; } Fraction& operator*=(const T&c){ return *this = (*this)*c; } Fraction& operator/=(const T&c){ return *this = (*this)/c; } Fraction& operator++(){ return (*this)+=1; } Fraction& operator--(){ return (*this)-=1; } Fraction& operator++(int){ return (*this)+=1; } Fraction& operator--(int){ return (*this)-=1; } Fraction operator+()const{ return *this; } Fraction operator-()const{ return Fraction(-num,den); } static Fraction raw(T a){ return Fraction(a,1); } Fraction pow(long long k)const{ Fraction res(1,1), tmp(*this); while(k){ if(k&1)res*=res; tmp*=tmp; k>>=1; } return res; } Fraction inv(){ return Fraction(den,num); } friend ostream& operator<<(ostream&os,const Fraction &a){os<<a.num<<"/"<<a.den;return os;} friend istream& operator>>(istream&is,Fraction &a){ is>>a.num;a.den=1; return is;} #define define_cmp(op) \ bool operator op (const Fraction& b) const{ return num*b.den op b.num*den; } define_cmp(==) define_cmp(!=) define_cmp(<) define_cmp(>) define_cmp(<=) define_cmp(>=) #undef define_cmp }; using ll=long long; using F=Fraction<ll>; void chmax(ll&a,ll b){ if(a<b)a=b; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n;cin>>n; vector<XY<ll>> xy(n); for(int i=0;i<n;i++)cin>>xy[i]; sort(xy.begin(),xy.end()); MinConvexHullTrick<F> CHT1; MaxConvexHullTrick<F> CHT2; ll ans=0; for(const auto&v:xy){ if(v.x==0){ chmax(ans,abs(xy[0].x * v.y)); chmax(ans,abs(xy.back().x * v.y)); continue; } if(CHT1.size()){ F res1=CHT1.query(F(v.y,v.x))*v.x, res2=CHT2.query(F(v.y/v.x))*v.x; assert(res1.den==1 and res2.den==1); chmax(ans, max(res1.num,res2.num)); } Line<F> f(F(v.x),F(-v.y)); CHT1.add(f); CHT2.add(f); } cout<<ans<<'\n'; }