結果
| 問題 |
No.3154 convex polygon judge
|
| ユーザー |
 Rubikun
|
| 提出日時 | 2025-05-20 21:25:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 73 ms / 2,000 ms |
| コード長 | 6,621 bytes |
| コンパイル時間 | 1,886 ms |
| コンパイル使用メモリ | 207,824 KB |
| 実行使用メモリ | 15,864 KB |
| 最終ジャッジ日時 | 2025-05-20 21:25:39 |
| 合計ジャッジ時間 | 3,586 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 44 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
//幾何ライブラリ(整数)
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);}
double norm(){return x*x+y*y;}
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;
ll norm(Vector a){
return a.x*a.x+a.y*a.y;
}
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;
}
struct Segment{
Point p1,p2;
};
bool isOrthogonal(Vector a,Vector b){
return dot(a,b)==0;
}
bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){
return isOrthogonal(a1-a2,b1-b2);
}
bool isOrthogonal(Segment s1,Segment s2){
return dot(s1.p2-s1.p1,s2.p2-s2.p1)==0;
}
bool isParallel(Vector a,Vector b){
return cross(a,b)==0;
}
bool isParallel(Point a1,Point a2,Point b1,Point b2){
return isParallel(a1-a2,b1-b2);
}
bool isParallel(Segment s1,Segment s2){
return cross(s1.p2-s1.p1,s2.p2-s2.p1)==0;
}
//p0,p1,p2の順に見たときどうなるか？
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;
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;
if(dot(a,b)<0) return online_back;
if(a.norm()<b.norm()) return online_front;
return on_segment;
}
bool intersect(Point p1,Point p2,Point p3,Point p4){
return(ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}
bool intersect(Segment s1,Segment s2){
return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}
bool overlap(Segment s1,Segment s2){
int a=ccw(s1.p1,s1.p2,s2.p1),b=ccw(s1.p1,s1.p2,s2.p2);
if(a&1||b&1) return 0;
if(a==2){
if(b==-2||(b==0&&!(s2.p2==s1.p1))) return 1;
else return 0;
}
if(a==-2){
if(b==2||(b==0&&!(s2.p2==s1.p2))) return 1;
else return 0;
}
if(a==0){
if(s1.p1==s2.p1){
if(b!=2) return 1;
else return 0;
}
else if(s1.p2==s2.p1){
if(b!=-2) return 1;
else return 0;
}
else return 1;
}
return 0;
}
//s1とs2の共通の線分(長さ0より大きい)があるかどうか
typedef Segment Line;
//ネットの適当を書いたのであってるか全く知りません→あってそう
class Circle{
public:
Point c;
ll r;
Circle(Point c=Point(),ll r=0.0):c(c),r(r){}
};
typedef vector<Point> Polygon;
/*
IN 2
ON 1
OUT 0
*/
int contains(Polygon g,Point p){
int n=int(g.size());
bool x=false;
for(int i=0;i<n;i++){
Point a=g[i]-p,b=g[(i+1)%n]-p;
if(a.y>b.y) swap(a,b);
if(a.y<=0&&0<b.y&&cross(a,b)<0) x=!x;
if(abs(cross(a,b))<=0&&dot(a,b)<=0) return 1;
}
return (x?2:0);
}
//ayasii
Polygon andrewScan(Polygon s,bool ok){
Polygon u,l;
sort(all(s));
if(int(s.size())<3) return s;
int n=int(s.size());
u.push_back(s[0]);
u.push_back(s[1]);
l.push_back(s[n-1]);
l.push_back(s[n-2]);
if(ok){
for(int i=2;i<n;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]);
}
}
if(!ok){
for(int i=2;i<n;i++){
for(int j=int(u.size());j>=2&&ccw(u[j-2],u[j-1],s[i])!=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])!=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;
}//ok==1なら辺の上も含める
ll area(Polygon P){
ll sum=0;
for(int i=0;i<si(P);i++){
sum+=cross(P[i],P[(i+1)%si(P)]);
}
return abs(sum);
}
// 倍
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
pair<Point,Vector> perpendicular_bisector(Point a,Point b){
Point c;
c.x=(a.x+b.x)/2;
c.y=(a.y+b.y)/2;
Vector v=b-c;
swap(v.x,v.y);
v.x*=-1;
Point p=c;
if(v.x==0){
v.y=1;
p.y=0;
}
else if(v.y==0){
v.x=1;
p.x=0;
}
else{
if(v.x<0){
v.x*=-1;
v.y*=-1;
}
ll g=gcd(abs(ll(v.x)),abs(ll(v.y)));
v.x/=g;
v.y/=g;
if(p.x>=0){
ll d=p.x/v.x;
p=p-v*d;
}else{
ll d=abs(p.x)/v.x;
p=p+v*d;
if(p.x<0){
p=p+v;
}
}
}
return mp(p,v);
}
//2倍するなりして整数にしておくこと
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int N;cin>>N;
vector<Point> P(N);
for(int i=0;i<N;i++){
cin>>P[i].x>>P[i].y;
}
auto Q=andrewScan(P,0);
if(si(Q)==N) cout<<"Yes\n";
else cout<<"No\n";
}