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

• 問題: No.2012 Largest Triangle
• ユーザー: cureskol
• 提出日時: 2023-02-12 18:23:17
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 217 ms / 2,500 ms
• コード長: 7,015 bytes
• コンパイル時間: 2,388 ms
• コンパイル使用メモリ: 217,880 KB
• 実行使用メモリ: 10,064 KB
• 最終ジャッジ日時: 2024-07-16 06:27:04
• 合計ジャッジ時間: 7,643 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	3 ms; 6,944 KB
testcase_02	AC	3 ms; 6,944 KB
testcase_03	AC	3 ms; 6,944 KB
testcase_04	AC	3 ms; 6,944 KB
testcase_05	AC	2 ms; 6,944 KB
testcase_06	AC	3 ms; 6,940 KB
testcase_07	AC	2 ms; 6,944 KB
testcase_08	AC	3 ms; 6,944 KB
testcase_09	AC	3 ms; 6,940 KB
testcase_10	AC	2 ms; 6,944 KB
testcase_11	AC	3 ms; 6,940 KB
testcase_12	AC	2 ms; 6,944 KB
testcase_13	AC	3 ms; 6,940 KB
testcase_14	AC	3 ms; 6,940 KB
testcase_15	AC	2 ms; 6,944 KB
testcase_16	AC	157 ms; 9,600 KB
testcase_17	AC	150 ms; 9,620 KB
testcase_18	AC	164 ms; 9,672 KB
testcase_19	AC	154 ms; 9,652 KB
testcase_20	AC	153 ms; 9,624 KB
testcase_21	AC	152 ms; 9,580 KB
testcase_22	AC	153 ms; 9,648 KB
testcase_23	AC	150 ms; 9,636 KB
testcase_24	AC	159 ms; 9,692 KB
testcase_25	AC	159 ms; 9,632 KB
testcase_26	AC	198 ms; 10,000 KB
testcase_27	AC	197 ms; 9,996 KB
testcase_28	AC	213 ms; 10,000 KB
testcase_29	AC	217 ms; 10,060 KB
testcase_30	AC	202 ms; 10,064 KB
testcase_31	AC	170 ms; 9,588 KB
testcase_32	AC	170 ms; 9,728 KB
testcase_33	AC	168 ms; 9,580 KB
testcase_34	AC	168 ms; 9,580 KB
testcase_35	AC	174 ms; 9,652 KB
testcase_36	AC	3 ms; 6,940 KB
testcase_37	AC	3 ms; 6,940 KB
testcase_38	AC	3 ms; 6,940 KB
testcase_39	AC	2 ms; 6,940 KB
testcase_40	AC	3 ms; 6,944 KB
testcase_41	AC	54 ms; 6,944 KB

ソースコード

#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){
    if(l.a==0 and l.b==0)os<<0;
    else if(l.a==0)os<<l.b;
    else if(l.b==0)os<<l.a<<"x";
    else if(l.b>0)os<<l.a<<"x+"<<l.b;
    else 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&l:lines)internal_push_back(l);
    }

    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;
    }

    friend ostream&operator<<(ostream&os,const ConvexHullTrick&cht){
      os<<"[";
      for(int i=0;i<cht.size();i++)
        os<<(OBJ==-1 ? -cht.at(i) : cht.at(i))<<"],"[i+1<cht.size()];
      if(!cht.size())os<<"]";
      return os;
    }
  };
}
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;}
};
using ll=long long;
using ld = long double;
void chmax(ld&a,ld b){ if(a<b)a=b; }

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;cin>>n;
  vector<XY<ld>> xy(n);
  for(int i=0;i<n;i++)cin>>xy[i];
  sort(xy.begin(),xy.end());

  MinConvexHullTrick<ld> CHT1;
  MaxConvexHullTrick<ld> CHT2;

  ld 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()){
      ld res1=CHT1.query(v.y/v.x)*v.x, res2=CHT2.query(v.y/v.x)*v.x;
      chmax(ans, max(abs(res1),abs(res2)));
    }
    Line<ld> f(v.x,-v.y);
    CHT1.add(f);
    CHT2.add(f);
  }
  cout<<ll(round(ans))<<'\n';
}