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

• 問題: No.2012 Largest Triangle
• ユーザー: cureskol
• 提出日時: 2023-02-12 17:51:36
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 9,372 bytes
• コンパイル時間: 2,795 ms
• コンパイル使用メモリ: 214,392 KB
• 最終ジャッジ日時: 2025-02-10 14:51:50
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 35 WA * 1 TLE * 5

ソースコード

#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(abs(res1.num),abs(res2.num)));
    }
    Line<F> f(F(v.x),F(-v.y));
    CHT1.add(f);
    CHT2.add(f);
  }
  cout<<ans<<'\n';
}