結果

問題 No.3154 convex polygon judge
ユーザー umezo
提出日時 2025-05-21 02:58:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 2,226 bytes
コンパイル時間 3,189 ms
コンパイル使用メモリ 287,228 KB
実行使用メモリ 18,164 KB
最終ジャッジ日時 2025-05-21 02:58:34
合計ジャッジ時間 5,386 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;
template <class T> using V=vector<T>;
template <class T> using VV=V<V<T>>;

static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;

class Point{
  public:
  ll x,y;
  
  Point(ll x=0, ll y=0): x(x),y(y) {}
  
  Point operator+(Point p){return Point(x+p.x,y+p.y);}
  Point operator-(Point p){return Point(x-p.x,y-p.y);}
  Point operator*(ll a){return Point(a*x,a*y);}
  Point operator/(ll a){return Point(x/a,y/a);}
  
  bool operator<(const Point &p) const{
    return x != p.x ? x<p.x : y<p.y;
  }
  
  bool operator==(const Point &p) const{
    return x==p.x && y==p.y;
  }
};
typedef Point Vector;
typedef vector<Point> Polygon;
ll dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
ll cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
int ccw(Point p0,Point p1,Point p2){
  Vector a=p1-p0;
  Vector b=p2-p0;
  if(cross(a,b)>0) return COUNTER_CLOCKWISE;
  if(cross(a,b)<0) return CLOCKWISE;
  return ON_SEGMENT;
}
//凸包(convex hull)  Polygon p; p.push_back(Point(x,y));
//辺上含まないときは==COUNTER_CLOCKWISEを!=CLOCKWISEに
Polygon andrewScan(Polygon s){
  Polygon u,l;
  if(s.size()<3) return s;
  sort(ALL(s));
  u.push_back(s[0]);
  u.push_back(s[1]);
  l.push_back(s[s.size()-1]);
  l.push_back(s[s.size()-2]);
  for(int i=2;i<(int)s.size();i++){
    for(int j=(int)u.size();j>=2 && ccw(u[j-2],u[j-1],s[i])!=COUNTER_CLOCKWISE;j--){
      u.pop_back();
    }
    u.push_back(s[i]);
  }
  for(int i=(int)s.size()-3;i>=0;i--){
    for(int j=(int)l.size();j>=2 && ccw(l[j-2],l[j-1],s[i])!=COUNTER_CLOCKWISE;j--){
      l.pop_back();
    }
    l.push_back(s[i]);
  }
  reverse(ALL(l));
  for(int i=(int)u.size()-2;i>=1;i--) l.push_back(u[i]);
  return l;
}

int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n;
  cin>>n;
  Polygon p;
  rep(i,n){
    ll x,y;
    cin>>x>>y;
    p.push_back(Point(x,y));
  }
  Polygon tmp=andrewScan(p);
  
  if(tmp.size()==n) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  return 0;
}
0