#779111 (C++17) No.2012 Largest Triangle

• 問題: No.2012 Largest Triangle
• ユーザー: eQe
• 提出日時: 2022-07-16 04:53:29
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 239 ms / 2,500 ms
• コード長: 11,524 bytes
• コンパイル時間: 13,207 ms
• コンパイル使用メモリ: 488,848 KB
• 実行使用メモリ: 20,444 KB
• 最終ジャッジ日時: 2023-09-10 11:21:17
• 合計ジャッジ時間: 22,059 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,352 KB
testcase_01	AC	1 ms; 4,352 KB
testcase_02	AC	1 ms; 4,356 KB
testcase_03	AC	2 ms; 4,356 KB
testcase_04	AC	2 ms; 4,356 KB
testcase_05	AC	1 ms; 4,356 KB
testcase_06	AC	2 ms; 4,356 KB
testcase_07	AC	2 ms; 4,356 KB
testcase_08	AC	2 ms; 4,356 KB
testcase_09	AC	2 ms; 4,356 KB
testcase_10	AC	2 ms; 4,356 KB
testcase_11	AC	2 ms; 4,356 KB
testcase_12	AC	2 ms; 4,356 KB
testcase_13	AC	2 ms; 4,356 KB
testcase_14	AC	2 ms; 4,356 KB
testcase_15	AC	2 ms; 4,360 KB
testcase_16	AC	214 ms; 19,828 KB
testcase_17	AC	215 ms; 19,736 KB
testcase_18	AC	215 ms; 20,420 KB
testcase_19	AC	216 ms; 20,096 KB
testcase_20	AC	213 ms; 19,632 KB
testcase_21	AC	215 ms; 19,996 KB
testcase_22	AC	214 ms; 19,900 KB
testcase_23	AC	215 ms; 19,880 KB
testcase_24	AC	220 ms; 20,024 KB
testcase_25	AC	216 ms; 19,832 KB
testcase_26	AC	238 ms; 20,444 KB
testcase_27	AC	235 ms; 20,164 KB
testcase_28	AC	236 ms; 20,248 KB
testcase_29	AC	231 ms; 20,424 KB
testcase_30	AC	236 ms; 20,300 KB
testcase_31	AC	231 ms; 19,896 KB
testcase_32	AC	232 ms; 20,160 KB
testcase_33	AC	233 ms; 20,012 KB
testcase_34	AC	234 ms; 19,916 KB
testcase_35	AC	239 ms; 19,968 KB
testcase_36	AC	3 ms; 4,352 KB
testcase_37	AC	3 ms; 4,352 KB
testcase_38	AC	3 ms; 4,356 KB
testcase_39	AC	3 ms; 4,352 KB
testcase_40	AC	3 ms; 4,356 KB
testcase_41	AC	70 ms; 9,500 KB

ソースコード

//#pragma GCC target("avx512f")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<atcoder/all>
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
#define fst first
#define snd second
#define len(a) (ll)size(a)
#define ppc(a) (ll)__builtin_popcountll(a)
#define sq(a) ((a)*(a))
#define bit(a) (1LL<<(a))
#define fin(...) exit(pr(__VA_ARGS__))
#define pb() pop_back()
#define ep(...) emplace(__VA_ARGS__)
#define eb(...) emplace_back(__VA_ARGS__)
#define ef(...) emplace_front(__VA_ARGS__)
#define ei(...) else if(__VA_ARGS__)
#define el else
#define wh(...) while(__VA_ARGS__)
#define lb(...) lower_bound(__VA_ARGS__)
#define ub(...) upper_bound(__VA_ARGS__)
#define srt(...) sort(all(__VA_ARGS__))
#define rev(...) reverse(all(__VA_ARGS__))
#define uni(a) srt(a);a.erase(unique(all(a)),end(a))
#define join(a,b) copy(all(b),back_inserter(a))
#define ov3(a,b,c,d,...) d
#define ov4(a,b,c,d,e,...) e
#define ov5(a,b,c,d,e,f,...) f
#define ov6(a,b,c,d,e,f,g,...) g
#define bg begin
#define rbg rbegin
#define all1(v) bg(v),end(v)
#define all2(v,b) bg(v),bg(v)+b
#define all3(v,a,b) bg(v)+a,bg(v)+b
#define all(...) ov3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rll1(v) rbg(v),rend(v)
#define rll2(v,b) rbg(v),rbg(v)+b
#define rll3(v,a,b) rbg(v)+a,rbg(v)+b
#define rll(...) ov3(__VA_ARGS__,rll3,rll2,rll1)(__VA_ARGS__)
#define rep1(b) for(ll ii=0;ii<(ll)(b);ii++)
#define rep2(i,b) for(ll i=0;i<(ll)(b);i++)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c))
#define rep(...) ov4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(a) rep(a)
#define per2(i,a) for(ll i=(ll)(a)-1;i>=0;i--)
#define per3(i,a,b) for(ll i=(ll)(a)-1;i>=(ll)(b);i--)
#define per4(i,a,b,c) for(ll i=(ll)(a)-1;i>=(ll)(b);i-=(ll)(c))
#define per(...) ov4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define foe1(a) rep(len(a))
#define foe2(a,v) for(au&&a:v)
#define foe3(a,b,v) for(au&&[a,b]:v)
#define foe4(a,b,c,v) for(au&&[a,b,c]:v)
#define foe5(a,b,c,d,v) for(au&&[a,b,c,d]:v)
#define foe(...) ov5(__VA_ARGS__,foe5,foe4,foe3,foe2,foe1)(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;lin(__VA_ARGS__)
#define ST(...) str __VA_ARGS__;lin(__VA_ARGS__)
#define UL2(n,a) u1 a(n);lin(a)
#define UL3(n,a,b) u1 a(n),b(n);lin(a,b)
#define UL4(n,a,b,c) u1 a(n),b(n),c(n);lin(a,b,c)
#define UL5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);lin(a,b,c,d)
#define UL6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);lin(a,b,c,d,e)
#define UL(...) ov6(__VA_ARGS__,UL6,UL5,UL4,UL3,UL2)(__VA_ARGS__)
#define UV2(n,a) u1 a(n);vin(a)
#define UV3(n,a,b) u1 a(n),b(n);vin(a,b)
#define UV4(n,a,b,c) u1 a(n),b(n),c(n);vin(a,b,c)
#define UV5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);vin(a,b,c,d)
#define UV6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);vin(a,b,c,d,e)
#define UV(...) ov6(__VA_ARGS__,UV6,UV5,UV4,UV3,UV2)(__VA_ARGS__)
#define DL2(n,a) v1<ld>a(n);lin(a)
#define DL3(n,a,b) v1<ld>a(n),b(n);lin(a,b)
#define DL4(n,a,b,c) v1<ld>a(n),b(n),c(n);lin(a,b,c)
#define DL5(n,a,b,c,d) v1<ld>a(n),b(n),c(n),d(n);lin(a,b,c,d)
#define DL(...) ov5(__VA_ARGS__,DL5,DL4,DL3,DL2)(__VA_ARGS__)
#define DV2(n,a) v1<ld>a(n);vin(a)
#define DV3(n,a,b) v1<ld>a(n),b(n);vin(a,b)
#define DV4(n,a,b,c) v1<ld>a(n),b(n),c(n);vin(a,b,c)
#define DV5(n,a,b,c,d) v1<ld>a(n),b(n),c(n),d(n);vin(a,b,c,d)
#define DV(...) ov5(__VA_ARGS__,DV5,DV4,DV3,DV2)(__VA_ARGS__)
#define I template
#define J class
#define oo operator
#define rr return
#define ss struct
#define uu using
#define as assert
#define au auto
#define bk break
#define bo bool
#define cs const
#define ct continue
#define endl "\n"
#define vo void
#define fn function
uu namespace atcoder;
uu namespace std;
uu namespace boost::multiprecision;
uu ll=long long;
uu ld=long double;
uu str=string;
I<J T>uu v1=vector<T>;
I<J T>uu v2=v1<v1<T>>;
I<J T>uu v3=v1<v2<T>>;
I<J T>uu v4=v1<v3<T>>;
I<J T>uu mset=multiset<T>;
uu u1=v1<ll>;
uu u2=v1<u1>;
uu u3=v1<u2>;
uu u4=v1<u3>;
uu pl=pair<ll,ll>;
uu ql=queue<ll>;
uu sl=set<ll>;
uu msl=mset<ll>;
uu ml=map<ll,ll>;
uu mnt=modint1000000007;
uu is=istream;
uu os=ostream;
ll inf=3e18;
ld pi=acosl(-1);
ld ee=1e-10;
str sp=" ";
str nc="";
str nl="\n";
str first(bo t=1){rr t?"first":"second";}
str First(bo t=1){rr t?"First":"Second";}
str yes(bo t=1){rr t?"yes":"no";}
str Yes(bo t=1){rr t?"Yes":"No";}
str YES(bo t=1){rr t?"YES":"NO";}
str no(){rr "no";}
str No(){rr "No";}
str NO(){rr "NO";}
str possible(bo t=1){rr t?"possible":"impossible";}
str Possible(bo t=1){rr t?"Possible":"Impossible";}
str POSSIBLE(bo t=1){rr t?"POSSIBLE":"IMPOSSIBLE";}
I<J T>uu heap_max=std::priority_queue<T>;
I<J T>uu heap_min=std::priority_queue<T,v1<T>,greater<T>>;
ll at(ll S,ll i){rr S>>i&1;}
I<J T>T at(cs v1<T>&v,ll i){ll n=len(v);rr v[(i%n+n)%n];}
I<J T>ll sig(cs T&a){rr(a>ee)-(a<-ee);}
I<J T>ll sig(cs T&a,cs T&b){rr sig(a-b);}
I<J T>v1<T>&oo+(v1<T>&v){rr v;}
I<J T>v1<T>&oo-(v1<T>&v){foe(x,v)x=-x;rr v;}
I<J T>v1<T>&oo++(v1<T>&v){foe(x,v)x++;rr v;}
I<J T>v1<T>&oo--(v1<T>&v){foe(x,v)x--;rr v;}
I<J T>v1<T>oo++(v1<T>&v,int){au r=v;++v;rr r;}
I<J T>v1<T>oo--(v1<T>&v,int){au r=v;--v;rr r;}
I<J T,J U>v1<T>&oo+=(v1<T>&v,cs U&a){foe(x,v)x+=a;rr v;}
I<J T,J U>v1<T>&oo-=(v1<T>&v,cs U&a){foe(x,v)x-=a;rr v;}
I<J T,J U>v1<T>&oo*=(v1<T>&v,cs U&a){foe(x,v)x*=a;rr v;}
I<J T,J U>v1<T>&oo/=(v1<T>&v,cs U&a){foe(x,v)x/=a;rr v;}
I<J T>v1<T>&oo+=(v1<T>&v,cs v1<T>&u){rep(i,len(v))v[i]+=u[i];rr v;}
I<J T>v1<T>&oo-=(v1<T>&v,cs v1<T>&u){rep(i,len(v))v[i]-=u[i];rr v;}
I<J T>v1<T>&oo*=(v1<T>&v,cs v1<T>&u){rep(i,len(v))v[i]*=u[i];rr v;}
I<J T>v1<T>&oo/=(v1<T>&v,cs v1<T>&u){rep(i,len(v))v[i]/=u[i];rr v;}
I<J T,J U>bo amax(T&a,cs U&b){rr a<b?a=b,1:0;}
I<J T,J U>bo amin(T&a,cs U&b){rr a>b?a=b,1:0;}
I<J T>T max(cs v1<T>&a){rr *max_element(all(a));}
I<J T>T min(cs v1<T>&a){rr *min_element(all(a));}
I<J T>ll argmax(cs v1<T>&a){rr max_element(all(a))-bg(a);}
I<J T>ll argmin(cs v1<T>&a){rr min_element(all(a))-bg(a);}
I<J...T>au max(T...a){rr max(initializer_list<common_type_t<T...>>{a...});}
I<J...T>au min(T...a){rr min(initializer_list<common_type_t<T...>>{a...});}
I<J T,J...A>T gcd(cs T&a,cs A&...b){rr gcd(a,gcd(b...));}
I<J T>T sum(cs v1<T>&a){rr aJumulate(all(a),T(0));}
I<J T>ll lbs(cs v1<T>&a,cs T&b){rr lb(all(a),b)-bg(a);}
I<J T>ll ubs(cs v1<T>&a,cs T&b){rr ub(all(a),b)-bg(a);}
I<J T>au mm(cs T&a,cs T&b){rr pair(min(a,b),max(a,b));}
I<J T>au mm(cs pair<T,T>&p){rr mm(p.fst,p.snd);}
u1 iota(ll n,ll a=0){u1 i(n);iota(all(i),a);rr i;}
vo emplace_front(u1&v,ll x=0){v.ep(bg(v),x);}
I<J X,J Y>au vmap(cs fn<Y(X)>&f,v1<X>x){v1<Y>y;foe(a,x)y.eb(f(a));rr y;}
I<J T,J U>au keys(cs map<T,U>&m){v1<T>r;foe(k,_,m)r.eb(k);rr r;}
I<J T,J U>au vals(cs map<T,U>&m){v1<U>r;foe(_,v,m)r.eb(v);rr r;}


ss _{_(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(10);}}_;
is&oo>>(is&i,mnt&x){ll t;i>>t;x=t;rr i;}
os&oo<<(os&o,cs mnt&x){rr o<<x.val();}
I<J T,J U>is&oo>>(is&i,pair<T,U>&p){rr i>>p.fst>>p.snd;}
I<J T,J U>os&oo<<(os&o,cs pair<T,U>&p){rr o<<p.fst<<sp<<p.snd;}
I<J T>is&oo>>(is&i,v1<T>&v){foe(x,v)i>>x;rr i;}
I<J T>os&oo<<(os&o,cs v1<T>&v){foe(x,v)o<<x<<(&x==&*rbg(v)?nc:sp);rr o;}
I<J T>os&oo<<(os&o,cs v2<T>&v){foe(x,v)o<<x<<(&x==&*rbg(v)?nc:nl);rr o;}
I<J T>os&oo<<(os&o,cs set<T>&s){foe(x,s)o<<x<<(&x==&*rbg(s)?nc:sp);rr o;}
I<J T>os&oo<<(os&o,cs mset<T>&s){foe(x,s)o<<x<<(&x==&*rbg(s)?nc:sp);rr o;}
I<J T,J U>os&oo<<(os&o,cs map<T,U>&m){foe(p,m)o<<p<<(&p==&*rbg(m)?nc:nl);rr o;}
I<J T>os&oo<<(os&o,queue<T>q){wh(len(q))o<<q.front()<<sp,q.pop();rr o;}
I<J T>os&oo<<(os&o,deque<T>q){wh(len(q))o<<q.front()<<sp,q.pop_front();rr o;}
I<J T>os&oo<<(os&o,heap_max<T>q){wh(len(q))o<<q.top()<<sp,q.pop();rr o;}
I<J T>os&oo<<(os&o,heap_min<T>q){wh(len(q))o<<q.top()<<sp,q.pop();rr o;}
ll pr(){cout<<endl;rr 0;}
ll db(){cerr<<endl;rr 0;}
I<J T,J...A>ll pr(cs T&a,cs A&...b){cout<<a;((cout<<sp<<b),...);rr pr();}
I<J T,J...A>ll db(cs T&a,cs A&...b){cerr<<a;((cerr<<sp<<b),...);rr db();}
I<J...T>vo lin(T&...a){(cin>>...>>a);}
I<J...T>vo vin(ll i,T&...a){(cin>>...>>a[i]);}
I<J T,J...A>vo vin(v1<T>&a,A&...b){rep(i,len(a))vin(i,a,b...);}
I<J T>vo rs(v1<T>&v,ll n){v.resize(n);}
I<J T,J...A>vo rs(v1<T>&V,ll n,cs A&...a){rs(V,n);foe(v,V)rs(v,a...);}
I<J T,J U>vo fl(T&x,cs U&a){x=a;}
I<J T,J U>vo fl(v1<T>&V,cs U&a){foe(v,V)fl(v,a);}


vo zi(cs u1&v,u1&h){foe(x,h)x=lbs(v,x);}
I<J...T>vo zi(cs u1&v,u1&h,T&...t){zi(v,h);zi(v,t...);}
I<J...T>u1 zip(T&...a){u1 v;foe(e,{a...})join(v,e);uni(v);zi(v,a...);rr v;}
I<J T>vo vs(cs u1&o,v1<T>&a){au c=a;rep(i,len(a))a[i]=c[o[i]];}
I<J T,J...A>vo vs(cs u1&o,v1<T>&a,A&...b){vs(o,a);vs(o,b...);}
I<J...T>au vsrt(cs fn<bo(ll,ll)>&f,T&...a){
  ll n=0;foe(e,{a...})n=len(e);
  u1 o=iota(n),p(n);
  sort(all(o),f);
  rep(i,n)p[o[i]]=i;
  vs(o,a...);
  rr pair(o,p);
}
I<J T>T bs(cs fn<bo(T)>&j,T o,T n){
  T d=(T)ee?ee:1;
  wh(abs(o-n)>d)(j((o+n)/2)?o:n)=(o+n)/2;
  rr o;
}
I<J T>au zt(v1<T>a){rep(i,1,len(a))a[i]+=a[i-1];rr a;}
I<J T>au mb(v1<T>a){per(i,len(a),1)a[i]-=a[i-1];rr a;}
I<J T>au zt(v2<T>a){foe(v,a)v=zt(v);rep(i,1,len(a))a[i]+=a[i-1];rr a;}
I<J T>au mb(v2<T>a){foe(v,a)v=mb(v);per(i,len(a),1)a[i]-=a[i-1];rr a;}
I<J T>T exq(ll n,T r,T x){wh(n){if(n&1)r*=x;x*=x;n/=2;}rr r;}
u1 dvs(ll n){ml m;rep(i,1,n/i+1)if(n%i==0)m[i]++,m[n/i]++;rr keys(m);}
ml fct(ll n){ml m;rep(i,2,n/i+1)wh(n%i==0)m[i]++,n/=i;if(n>1)m[n]++;rr m;}
ll pom(ll x,ll n,ll m=inf){ll r=1;wh(n){if(n&1)r*=x,r%=m;x*=x,x%=m,n/=2;}rr r;}
ll inv(ll a,ll m){
  ll b=m,u=1,v=0;
  wh(b)u-=a/b*v,swap(u,v),a-=a/b*b,swap(a,b);
  rr(u%m+m)%m;
}
ll sqr(ll x){ll r=sqrtl(x)-1;wh(r+1<=x/(r+1))r++;rr r;}
ll lg2(ll n){ll r=0;wh(n){n/=2;r++;}rr r;}
u1 dx={-1,0,1,0,-1,1,1,-1};
u1 dy={0,-1,0,1,-1,-1,1,1};


ss edg{ll t,w;edg(){}edg(ll t,ll w=1):t(t),w(w){}};
uu graph=v2<edg>;
vo GR(u2&g,ll m,bo d=1){rep(i,m){LL(a,b);a--;b--;g[a].eb(b);if(d)g[b].eb(a);}}
vo GR(graph&g,ll m,bo w=1,bo d=1){
  rep(i,m){
    LL(a,b);a--;b--;ll c=1;
    if(w)lin(c);
    g[a].eb(b,c);
    if(d)g[b].eb(a,c);
  }
}
vo TR(u2&g,bo d=1){GR(g,len(g)-1,d);}
vo TR(graph&g,bo w=1,bo d=1){GR(g,len(g)-1,w,d);}
vo wf(u2&d){ll n=len(d);rep(k,n)rep(i,n)rep(j,n)amin(d[i][j],d[i][k]+d[k][j]);}


uu S=ll;
S emax(){rr-inf;}
S emin(){rr inf;}
S add(S a,S b){rr a+b;}
S eadd(){rr 0;}
S ope(S a,S b){rr a+b;}
S einh(){rr 0;}
uu seg_max=segtree<S,max,emax>;
uu seg_min=segtree<S,min,emin>;
uu seg_add=segtree<S,add,eadd>;
uu seg_oth=segtree<S,ope,einh>;


I<J T>ss convex_hull_trick{
  ss p{
    T a,b;
    p(T a,T b):a(a),b(b){}
    bo oo<(cs p&p)cs{rr sig(a,p.a)?sig(a,p.a)<0:sig(b,p.b)<0;}
    friend os&oo<<(os&o,cs p&p){rr o<<p.a<<sp<<p.b;}
  };
  deque<p>ls;
  convex_hull_trick(){}
  
  bo check(p l1,p l2,p l3){
    if(l1<l3)swap(l1,l3);
    rr(l3.b-l2.b)*(l2.a-l1.a)>=(l2.b-l1.b)*(l3.a-l2.a);
  }
  vo add(T a,T b){
    p l(a,b);
    wh(len(ls)>=2 and check(*(ls.end()-2),*(ls.end()-1),l))ls.pb();
    ls.eb(l);
  }
  T f(ll i,T x){rr ls[i].a*x+ls[i].b;}
  T get(T x){
    ll l=0,r=len(ls)-1;
    wh(l+1<r){
      ll m=(l+r)/2;
      (f(m,x)>=f(m+1,x)?l:r)=m;
    }
    rr f(r,x);
  }
};


int main(){
  LL(N);
  DV(N,a,b);
  
  vsrt([&](ll i,ll j){rr sig(b[i],b[j])?sig(b[i],b[j])<0:sig(a[i],a[j])<0;},a,b);
  convex_hull_trick<ld>cht_max,cht_min;
  rep(i,N)cht_min.add(-b[i],a[i]);
  per(i,N)cht_max.add(b[i],-a[i]);
  
  
  ld ans=0;
  ld t=0;
  rep(i,N){
    if(b[i]){
      amax(ans,abs(b[i]*cht_max.get(a[i]/b[i])));
      amax(ans,abs(b[i]*cht_min.get(a[i]/b[i])));
    }el{
      amax(t,abs(a[i]));
    }
  }
  amax(ans,t*max(vmap<ld,ld>([&](ld x){rr abs(x);},b)));
  pr(llroundl(ans));
}