結果
| 問題 |
No.3154 convex polygon judge
|
| コンテスト | |
| ユーザー |
 batapi0311
|
| 提出日時 | 2025-05-21 02:48:15 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 106 ms / 2,000 ms |
| コード長 | 18,377 bytes |
| コンパイル時間 | 8,437 ms |
| コンパイル使用メモリ | 325,708 KB |
| 実行使用メモリ | 28,908 KB |
| 最終ジャッジ日時 | 2025-05-21 02:48:26 |
| 合計ジャッジ時間 | 9,701 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 44 |
ソースコード
#include <bits/stdc++.h>
//#include <ranges>
#define _USE_MATH_DEFINES
//aclをatcoder以外で使うときは'combine [ファイル名]'とターミナルに打てばよい
// #include <atcoder/dsu>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint1000000007;
using namespace std;
// using mint = modint;
using ll = long long;
using ld = long double;
using lll=__int128_t;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define V vector<ll>
#define Vi vector<int>
#define Vd vector<double>
#define Vld vector<long double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define VV vector<V>
using P = pair<ll,ll>;
using G = vector<vector<ll>>;
#define VP vector<P>
#define VT vector<tuple<ll,ll,ll>>
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define INF 1LL << 60
#define inf 1e9
template <typename T>
bool chmax(T &a, const T& b) {
if (a < b) {
a = b; // aをbで更新
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
if (a > b) {
a = b; // aをbで更新
return true;
}
return false;
}
long long combi(long long n, long long k) {
if (n == k || k == 0)
return 1;
else {
return combi(n - 1, k - 1) + combi(n - 1, k);
}
}
//二項係数
#define CMAX 1010
int noinit = 1; ll acbmemo[CMAX][CMAX];
ll aCb(ll a, ll b) {
if (noinit) {
rep2(i, 0, CMAX) rep2(j, 0, CMAX) acbmemo[i][j] = -1;
noinit = 0;
}
if (b == 0 || a == b) return 1;
if (0 <= acbmemo[a][b]) return acbmemo[a][b];
return acbmemo[a][b] = aCb(a - 1, b - 1) + aCb(a - 1, b);
}
//整数かどうか
bool isNumber(const string& str)
{
for (const char &c : str) {
if (std::isdigit(c) == 0) return false;
}
return true;
}
///*
//最大公約数
ll gcd(ll a, ll b){
if(b==0){
return a;
}else{
return gcd(b, a%b);
}
}
//最小公倍数
ll lcm(ll a, ll b){
ll g=gcd(a,b);
return a/g*b;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
//*/
//int di[] = {-1,0,1,0};
//int dj[] = {0,-1,0,1};
//s = regex_replace(s, regex("あ"), "う");
/*stiring で char を検索するときは
s.find(c)!=string::npos
*/
/*//各桁の和
int wa(int n){
int sum =0;
while(n>0){
sum += n%10;
n/=10;
}
return sum;
}
*/
//
/*
//階乗
int ki(int i){
int k = 1;
for(int j = 1; j<=i; j++){
k *= j;
}
return k;
}
//
*/
/*log_x(b)
double logN(double x, double b) {
return log(x) / log(b);
}
*/
///*
//エラトステネスの篩O(NloglogN) main関数内にSieveofEratosthenes();を書き込む!!
const ll N = 5050505;//求める範囲
Vb isp(N+1,true);
void SieveofEratosthenes(){
isp[0] = false;
isp[1] = false;
for(ll i = 2; i+i<=N;i++){
if(isp[i])for(ll j = 2; i*j<=N;j++)isp[i*j] = false;
}
}
//*/
///*
//約数列挙 O(√n)
vector<long long> divisor(long long n) {
vector<long long> ret;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(ret.begin(), ret.end()); // 昇順に並べる
return ret;
}
//*/
//
/*
//素因数分解O(√n)
map< ll, ll > prime_factor(ll n) {
map< ll, ll > ret;
for(ll i = 2; i * i <= n; i++) {
while(n % i == 0) {
ret[i]++;
n /= i;
}
}
if(n != 1) ret[n] = 1;
return ret;
}
//
*/
/*
ll modpow(ll x, ll n, ll mod){
while(n){
ll resu = 1;
if(n&1)res = (res * x) %mod;
x = (x*x)%mod;
n>>=1;
}
return res;
}
*/
///*
//最小二乗法
//aのb乗をmで割ったあまりを返す関数
//変数aはa^1→a^2→a^4→a^8→…と変化
ll power(ll a,ll b, ll m){
ll p = a,ans = 1;
rep(i,60){
ll wari = (1LL<<i);
if((b/wari)%2==1){
ans=(ans*p)%m;
}
p=(p*p)%m;
}
return ans;
}
//*/
//
/*
//0~xまでのxor累積和
ll xor_sum(ll x){
if(x%2!=0){
x-1;
if((x/2)%2==0)return 1;
else return 0;
}else{
if(x%4==0)return x;
else return x+1;
}
}
//
*/
/*
template <typename T> bool next_combination(const T first, const T last, int k) {
const T subset = first + k;
// empty container | k = 0 | k == n
if (first == last || first == subset || last == subset) {
return false;
}
T src = subset;
while (first != src) {
src--;
if (*src < *(last - 1)) {
T dest = subset;
while (*src >= *dest) {
dest++;
}
iter_swap(src, dest);
rotate(src + 1, dest + 1, last);
rotate(subset, subset + (last - dest) - 1, last);
return true;
}
}
// restore
rotate(first, subset, last);
return false;
}
//
*/
int ctoi(char c){
if(c>='0' and c<='9')return c-'0';
else return -inf;
}
char touplo(char c){
char ret=c;
ret^=32;
return ret;
}
//vector<int> dx = {1,0,-1,0,1,-1,-1,1};
//vector<int> dy = {0,1,0,-1,1,1,-1,-1};
//時計回り
int clx[4] = { 0, 1, 0, -1}, cly[4] = { -1, 0, 1, 0 };
//反時計回り
int cclx[4] = { 0, -1, 0, 1}, ccly[4] = { -1, 0, 1, 0 };
int dx[8] = { 0, 1, 0, -1, 1, 1, -1, -1 }, dy[8] = { 1, 0, -1, 0, 1, -1, 1, -1 };
// int dx[8]={0,-1,-1,-1,0,1,1,1},dy[8]={1,1,0,-1,-1,-1,0,1};
//#define mod 998244353
//cout << mint.val() << endl;
//cout << fixed << setprecision(15) << y << endl;
P mima(int a,int b){
P ret;
ret=make_pair(min(a,b),max(a,b));
return ret;
}
//bit s に i番目のビットを立てる
#define bittate(s,i) (s|(1LL<<i))
//bit sから i番目のビットを消す
#define bitkeshi(s,i) (s^(1LL<<i))
//bit s が i番目のビットを含んでいるか
bool bitcheck(ll s,ll i){
if((s>>i)&1LL)return true;
else return false;
}
//string str(bitset<32>(value).to_string<char, char_traits<char>, allocator<char> >());
#define ppc(n) __popcount(n)
string lltobin(ll n){
string re((bitset<61>(n).to_string<char, char_traits<char>, allocator<char> >()));
return re;
}
ll bintoll(string s){
ll re=stoll(s,nullptr,2);
return re;
}
//-1なら外れてる、それ以外なら座標を1次元に変換
ll kabe_check(ll i,ll j,ll h,ll w){
if((i<0 or h<=i or j<0 or w<=j))return -1;
else return i*w+j;
}
#define yes "Yes"
#define no "No"
#define Yes "YES"
#define No "NO"
#include<complex>
namespace geometry{
using ld=long double;
using point=complex<ld>;
const ld eps=1e-9;
const ld PI=acos(ld(-1));
inline bool equal(const ld &a,const ld &b){
return fabs(a-b)<eps;
}
//単位ベクトル
point unitVector(const point &a){
return a/abs(a);
}
//法線ベクトル
point normalVector(const point &a){
return a*point(0,1);
}
//内積: a*b=|a||b|cosθ
ld dot(const point &a, const point &b){
return (a.real()*b.real()+a.imag()*b.imag());
}
//外積: a×b=|a||b|sinθ
ld cross(const point &a, const point &b){
return (a.real()*b.imag()-a.imag()*b.real());
}
//反時計回りに回転(ラジアン)
point rotate(const point &p, const ld &theta){
return point(cos(theta)*p.real()-sin(theta)*p.imag(),
sin(theta)*p.real()+cos(theta)*p.imag());
}
//ラジアンー＞度
ld radianTodegree(const ld &radian){return radian *180/PI;}
//度ー＞ラジアン
ld degreeToradian(const ld °ree){return degree *PI/180;}
//点の回転方向
//点aを基準にしてb,cの位置関係
int ccw(const point &a, point b,point c){
b-=a,c-=a;
//反時計回りのときー＞１
if(cross(b,c)>eps)return 1;
//時計回りのときー＞－１
if(cross(b,c)<-eps)return -1;
//c,a,bがこの順で同一直線上にあるとき
if(dot(b,c)<0)return 2;
//a,b,cがこの順で同一直線上にあるとき
if(norm(b)<norm(c))return -2;
//cが線分ab上にあるとき
return 0;
}
//Line:直線
//b-aで直線・線分
struct Line{
point a,b;
Line()=default;
Line(point a, point b) : a(a),b(b){}
//ax+by=c
Line(ld A, ld B, ld C){
if(equal(A,0)){
a=point(0,C/B),b=point(1,C/B);
}else if(equal(B,0)){
b=point(C/A,0),b=point(C/A,1);//ホントにb⁇
}else{
a=point(0,C/B),b=point(C/A,0);
}
}
};
//線分
struct Segment : Line{
Segment()=default;
Segment(point a, point b):Line(a,b){}
ld get_dist(){return abs(a-b);}
};
//円
//pが中心の位置ベクトル，rは半径
struct circle{
point p;
ld r;
circle()=default;
circle(point p, ld r) : p(p),r(r){};
};
//2直線の直交判定 内積0
bool isOrthogonal(const Line &a, const Line &b){
return equal(dot(a.b-a.a,b.b-b.a),0);
}
//2直線の平行判定 外積0
bool isParaleel(const Line &a, const Line &b){
return equal(cross(a.b-a.a,b.b-b.a),0);
}
//点cが直線ab上にあるか
bool isPointOnLine(const point &a,const point &b, const point &c){
return isParaleel(Line(a,b),Line(a,c));
}
//点cが線分ab上にあるか
bool isPointOnSegment(const point &a, const point &b, const point &c){
//|a-c|+|c-b|<=|a-b|なら線分上
return (abs(a-c)+abs(c-b)<abs(a-b)+eps);
}
//直線lと点pのキョリ
ld distanceBetweenLineAndPoint(const Line &l, const point &p){
return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a);
}
//線分lと点pのキョリを求める
//点pから線分lのどこかへの最短距離
ld distanceBetweenSegmentAndPoint(const Segment &l, const point &p){
if(dot(l.b-l.a,p-l.a)<eps)return abs(p-l.a);
if(dot(l.a-l.b,p-l.b)<eps)return abs(p-l.b);
return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a);
}
//直線s,tの交点
point crossPoint(const Line &s, const Line &t){
ld d1=cross(s.b-s.a,t.b-t.a);
ld d2=cross(s.b-s.a,s.b-t.a);
if(equal(abs(d1),0) and equal(abs(d2),0))return t.a;
return t.a+(t.b-t.a)*(d2/d1);
}
//線分s,tの交点
point crossPoint(const Segment &s,const Segment &t){
return crossPoint(Line(s),Line(t));
}
//線分sと線分tが交差しているか
//bound:線分の境界を含むか
bool isIntersect(const Segment &s, const Segment &t, bool bound){
return ccw(s.a,s.b,t.a)*ccw(s.a,s.b,t.b)<bound and
ccw(t.a,t.b,s.a)*ccw(t.a,t.b,s.b)<bound;
}
//線分s,t間のキョリ
ld distanceBetweenSegments(const Segment &s,const Segment &t){
if(isIntersect(s,t,1))return (ld)(0);
ld ans=distanceBetweenSegmentAndPoint(s,t.a);
ans=min(ans,distanceBetweenSegmentAndPoint(s,t.b));
ans=min(ans,distanceBetweenSegmentAndPoint(t,s.a));
ans=min(ans,distanceBetweenSegmentAndPoint(t,s.b));
return ans;
}
//射影(projection)
//直線(線分)lに点pから引いた垂線の足を求める
point projection(const Line &l, const point &p){
ld t=dot(p-l.a,l.a-l.b)/norm(l.a-l.b);
return l.a+(l.a-l.b)*t;
}
point projection(const Segment &l, const point &p){
ld t=dot(p-l.a,l.a-l.b)/norm(l.a-l.b);
return l.a+(l.a-l.b)*t;
}
//反射(reflection)
//直線lを対象軸として点pと線対称の位置にある点
point reflection(const Line &l, const point &p){
return p+(projection(l,p)-p)*(ld)2.0;
}
//2円の交差判定
//返り値は共通接戦の数
int isIntersect(const circle &c1, const circle &c2){
ld d=abs(c1.p-c2.p);
//2円が離れているとき
if(d>c1.r+c2.r+eps)return 4;
//外接しているとき
if(equal(d,c1.r+c2.r))return 3;
//内接しているとき
if(equal(d,abs(c1.r-c2.r)))return 1;
//内包しているとき
if(d<abs(c1.r-c2.r)-eps)return 0;
return 2;
}
//2円の交点
vector<point> crossPoint(const circle &c1, const circle &c2){
vector<point>ret;
int mode=isIntersect(c1,c2);
//2円の中心間のキョリ
ld d=abs(c1.p-c2.p);
//2円が離れているとき
if(mode==4)return ret;
//一方の円が他方の円に内包されているとき
if(mode==0)return ret;
//2円が外接するとき
if(mode==3){
ld t=c1.r/(c1.r+c2.r);
ret.emplace_back(c1.p+(c2.p-c1.p)*t);
return ret;
}
//内接しているとき
if(mode==1){
if(c2.r<c1.r-eps){
ret.emplace_back(c1.p+(c2.p-c1.p)*(c1.r/d));
}else{
ret.emplace_back(c2.p+(c1.p-c2.p)*(c2.r/d));
}
return ret;
}
//2円が重なるとき
ld rc1=(c1.r*c1.r+d*d-c2.r*c2.r)/(2*d);
ld rs1=sqrt(c1.r*c1.r-rc1*rc1);
if(c1.r-abs(rc1)<eps)rs1=0;
point e12=(c2.p-c1.p)/abs(c2.p-c1.p);
ret.emplace_back(c1.p+rc1*e12+rs1*e12*point(0,1));
ret.emplace_back(c1.p+rc1*e12+rs1*e12*point(0,-1));
return ret;
}
//点pが円cの内部(円周上も含む)に入っているかどうか
bool isIncircle(const circle &c, const point &p){
ld d=abs(c.p-p);
return (equal(d,c.r) or d<c.r-eps);
}
//円cと直線lの交点
vector<point> crossPoint(const circle &c, const Line &l){
vector<point> ret;
ld d=distanceBetweenLineAndPoint(l,c.p);
//交点を持たない
if(d>c.r+eps)return ret;
//接する
point h=projection(l,c.p);
if(equal(d,c.r)){
ret.emplace_back(h);
return ret;
}
point e=unitVector(l.b-l.a);
ld ph=sqrt(c.r*c.r-d*d);
ret.emplace_back(h-e*ph);
ret.emplace_back(h+e*ph);
return ret;
}
//点pを通る円cの接線
//2本あるので接点のみを返す
vector<point> tangentToCircle(const point &p, const circle &c){
return crossPoint(c,circle(p,sqrt(norm(c.p-p)-c.r*c.r)));
}
//円の共通接線
vector<Line> tangent(const circle &a, const circle &b){
vector<Line>ret;
//2円の中心間のキョリ
ld g=abs(a.p-b.p);
if(equal(g,0))return ret;
point u=unitVector(b.p-a.p);
point v=rotate(u,PI/2);
for(int s : {-1,1}){
ld h=(a.r+b.r*s)/g;
if(equal(h*h,1)){
ret.emplace_back(a.p+(h>0 ? u:-u)*a.r,
a.p+(h>0 ? u:-u)*a.r+v);
}else if(1-h*h>0){
point U=u*h,W=v*sqrt(1-h*h);
ret.emplace_back(a.p+(U+W)*a.r,
b.p-(U+W)*(b.r*s));
ret.emplace_back(a.p+(U-W)*a.r,
b.p-(U-W)*(b.r*s));
}
}
return ret;
}
//多角形の面積を求める
ld polygonArea(const vector<point> &p){
ld ret=0;
int n=p.size();
for(int i=0; i<n-1; i++)ret+=cross(p[i],p[i+1]);
ret+=cross(p[n-1],p[0]);
return ret*0.5;
}
//凸多角形かどうか
bool isConvex(const vector<point> &p){
int n=p.size();
int now,pre,nxt;
for(int i=0;i<n;i++){
pre=(i-1+n)%n;
nxt=(i+1)%n;
now=i;
if(ccw(p[pre],p[now],p[nxt])==-1)return false;
}
return true;
}
//凸包O(NlogN)
vector<point> ConvexHull(vector<point> p){
int n=(int)p.size(),k=0;
sort(p.begin(),p.end(),[](const point &a, const point &b){
return (a.real()!=b.real() ? a.real()<b.real() : a.imag()<b.imag());
});
vector<point> ch(2*n);
//一直線上の3点を含める->(<eps)
//含めない->(<eps)
for(int i=0; i<n; ch[k++]=p[i++]){
while(k>=2 and
cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<eps)k--;
}
for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){
while(k>=t and
cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<eps)k--;
}
ch.resize(k-1);
return ch;
}
//多角形gに点pが含まれているか
//含まれる：2，辺上にある：1，含まれない:0
int isContained(const vector<point> &g, const point &p){
bool in =false;
int n=(int)g.size();
for(int i=0;i<n;i++){
point a=g[i]-p,b=g[(i+1)%n]-p;
if(imag(a)>imag(b))swap(a,b);
if(imag(a)<=eps and eps<imag(b) and cross(a,b)<-eps)in=!in;
if(cross(a,b)==0 and dot(a,b)<=0)return 1;
}
return (in ? 2 : 0);
}
// 凸多角形pを直線lで切断し、その左側を返す
vector<point> convexCut(vector<point> p, Line l){
vector<point> ret;
int sz=(int)p.size();
for(int i=0;i<sz;i++){
point now=p[i];
point nxt=p[i==sz-1 ? 0 : i+1];
if(ccw(l.a,l.b,now)!=-1)ret.emplace_back(now);
if(ccw(l.a,l.b,now)*ccw(l.a,l.b,nxt)<0){
ret.emplace_back(crossPoint(Line(now,nxt),l));
}
}
return ret;
}
}
using namespace geometry;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<point> p(n);
rep(i,n){
int a,b;
cin >> a >> b;
p[i].real(a);
p[i].imag(b);
}
auto e=ConvexHull(p);
if(e.size()==n)cout << yes << endl;
else cout << no << endl;
}