QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242032 | #7730. Convex Checker | invaded | WA | 0ms | 3896kb | C++17 | 13.0kb | 2023-11-06 21:23:44 | 2023-11-06 21:23:44 |
Judging History
你现在查看的是最新测评结果
- [2024-07-04 19:27:17]
- hack成功,自动添加数据
- (/hack/727)
- [2024-07-04 19:17:30]
- hack成功,自动添加数据
- (/hack/726)
- [2023-12-08 14:40:48]
- hack成功,自动添加数据
- (//qoj.ac/hack/493)
- [2023-11-07 10:32:52]
- hack成功,自动添加数据
- (//qoj.ac/hack/426)
- [2023-11-07 10:28:41]
- hack成功,自动添加数据
- (//qoj.ac/hack/425)
- [2023-11-06 21:23:44]
- 提交
answer
#include<bits/stdc++.h>
#ifndef xxx
#define dbg(...) ;
#endif
using namespace std;
template<class T> ostream &operator<<(ostream &o, const vector <T> &v) { bool f=false; for(T i:v) { f?o<<' ':o; o<<(i); f=true; } return o; }
template<class T> void sort(T &v) { std::sort(v.begin(), v.end()); }
template<class T, class C> void sort(T &v, C c) { std::sort(v.begin(), v.end(), c); }
template<class T> void reverse(T &v) { std::reverse(v.begin(), v.end()); }
template<class T> bool is_sorted(T &v) { return std::is_sorted(v.begin(), v.end()); }
template<class T> inline void _min(T &x, const T &y) { x>y?x=y:x; }
template<class T> inline void _max(T &x, const T &y) { x<y?x=y:x; }
istream &operator>>(istream &i, __int128_t &x) { x=0; short f=1; char c=0; while(!isdigit(c)) { if(c=='-')f=-1; c=i.get(); } while(isdigit(c))x=x*10+c-'0', c=i.get(); x*=f; return i; }
ostream &operator<<(ostream &o, __int128_t x) { if(x==0) { o<<0; return o; } bool f=false; string s; if(x<0)f=true, x=-x; while(x)s+=x%10+'0', x/=10; reverse(s); if(f)o<<'-'; o<<s; return o; }
mt19937 mt(time(0));
//typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
constexpr int maxn=2e5+5;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3fll;
constexpr double pi=acos(-1.0);
constexpr double eps=1e-9;
namespace geometry
{
//db toRadian(const db a) { return pi*a/180; }
/**
* a==b sgn(a-b)==0
* a!=b sgn(a-b)!=0
* a<b sgn(a-b)<0
* a<=b sgn(a-b)<=0
* a>b sgn(a-b)>0
* a>=b sgn(a-b)>=0
*/
int sgn(double x)
{
if(abs(x)<eps)return 0;
return x<0?-1:1;
}
using gtype=ll;
template <class T>
struct Point_t
{
using db=T;
using Point=Point_t;
db x, y;
Point_t() :x(0), y(0) {}
Point_t(db x, db y) :x(x), y(y) {}
// y<P.y x<P.x
bool operator<(const Point &P)const { return y==P.y?x<P.x:y<P.y; }
bool operator==(const Point &P)const { return x==P.x&&y==P.y; }
bool operator!=(const Point &P)const { return x!=P.x||y!=P.y; }
bool operator>(const Point &P)const { return operator!=(P)&&!operator<(P); }
/**
*@param rad radian rad<0: anticlockwise, rad>0: clockwise
*@note rotate first, translate second
*/
Point rotateOrigin(const db rad) { return Point(x*cos(rad)+y*sin(rad), y*cos(rad)-x*sin(rad)); }
/**
*@param rad radian rad<0: anticlockwise, rad>0: clockwise
*@param P Rotate around point P
*@note rotate first, translate second
*/
Point rotate(const Point &P, const db rad) { return Point((x-P.x)*cos(rad)+(y-P.y)*sin(rad)+P.x, (y-P.y)*cos(rad)-(x-P.x)*sin(rad)+P.y); }
/**
*@return new Point
*@note rotate first, translate second
*/
Point translateOrigin(const db dx, const db dy) { return Point(x-dx, y-dy); }
db dis2(const Point &p)const { return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y); }
db dis(const Point &p)const { return sqrt(dis2(p)); }
friend istream &operator>>(istream &i, Point &P) { i>>P.x>>P.y; return i; }
friend ostream &operator<<(ostream &o, const Point &p) { o<<"("<<p.x<<", "<<p.y<<")"; return o; }
};
typedef Point_t<gtype> Point;
template<class T>
struct Vect_t
{
using db=T;
using Vect=Vect_t;
db x, y;
Vect_t() {}
Vect_t(const Point &p) :x(p.x), y(p.y) {}
Vect_t(db x, db y) :x(x), y(y) {}
Vect_t(const Point &st, const Point &ed) :x(ed.x-st.x), y(ed.y-st.y) {}
Vect operator+(const Vect &V)const { return Vect(x+V.x, y+V.y); }
Vect operator-(const Vect &V)const { return Vect(x-V.x, y-V.y); }
Vect operator*(db k)const { return Vect(x*k, y*k); }
Vect operator/(db k)const { return Vect(x/k, y/k); }
friend Vect operator*(const db &k, const Vect &V) { return V.operator*(k); }
friend Vect operator/(const db &k, const Vect &V) { return V.operator/(k); }
db dot(const Vect &V)const { return x*V.x+y*V.y; }
db cross(const Vect &V)const { return x*V.y-y*V.x; }
/**
* @brief to-left test
* @return res: V is on the left of *this if res>0;
* V is parallel with *this if res=0;
* V is on the right of *this if res<0
*/
int toLeft(const Vect &V)const { db t=cross(V); return (t>0)-(t<0); }
/**
* @brief angle of rotation
* @param V rotate from *this to V
* @return `r`(in radians): By rotating *this `r` radians, we can obtain the vector V
*/
db getRotationAngle(const Vect &V) { return acos(dot(V)/(V.len()*len()))*(toLeft(V)>0?-1:1); }
bool is_parallel(const Vect &V)const { return cross(V)==0; }
bool is_vertical(const Vect &V)const { return dot(V)==0; }
db len2()const { return x*x+y*y; }
db len()const { return sqrt(len2()); }
/**
* normal().dot(*this)=0
* @return normal vector
*/
Vect normal()
{
db length=len();
if(length==0)return Vect(0, 0);
return Vect(-y/length, x/length);
}
/**
*@param rad radian rad<0: anticlockwise, rad>0: clockwise
*@note use it when the origin rorates
*/
Point rotateOrigin(const db &rad) { return Point(x*cos(rad)+y*sin(rad), y*cos(rad)-x*sin(rad)); }
friend ostream &operator<<(ostream &o, const Vect &V) { o<<"("<<V.x<<", "<<V.y<<")"; return o; }
};
typedef Vect_t<gtype> Vect;
Vect operator-(const Point &a, const Point &b) { return Vect(a.x-b.x, a.y-b.y); }
template<class T>
struct Segment_t
{
using db=T;
using Segment=Segment_t;
Point st, ed;
Segment_t() {}
Segment_t(const Point &st, const Point &ed) :st(st), ed(ed) {}
bool is_on(const Point &P)const { return Vect(st, P).cross(Vect(ed, P))==0&&Vect(st, P).dot(Vect(ed, P))<=0; }
db dis(const Point &P)const
{
if((P-st).dot(ed-st)<0)return (P-st).len();
if((P-ed).dot(st-ed)<0)return (P-ed).len();
return abs((st-P).cross(ed-P)/len());
}
db len2()const { db x=ed.x-st.x, y=ed.y-st.y; return x*x+y*y; }
db len()const { return sqrt(len2()); }
Point mid()const { return Point((st.x+ed.x)/2, (st.y+ed.y)/2); }
friend ostream &operator<<(ostream &o, const Segment &s) { o<<"[ "<<s.st<<' '<<s.ed<<" ]"; return o; }
};
typedef Segment_t<gtype> Segment;
//v: st.y<ed.y or (st.y=ed.y and st.x<ed.x)
template<class T>
struct Line_t
{
using db=T;
using Line=Line_t;
Point p;
// @note v.y>0 or (v.y=0 and v.x>0)
Vect v;
Line_t() {}
Line_t(const Point &p, const Vect &v) :p(p), v(v) {}
Line_t(Point p1, Point p2)
{
// to ensure that p1.y<p2.y or (p1.y=p2.y and p1.x<p2.x)
if(p1.y>p2.y)swap(p1, p2);
if(p1.y==p2.y&&p1.x>p2.x)swap(p1, p2);
p=p1;
v=p2-p1;
}
Line_t(const Segment &S)
{
auto p1=S.st;
auto p2=S.ed;
// to ensure that p1.y<p2.y or (p1.y=p2.y and p1.x<p2.x)
if(p1.y>p2.y)swap(p1, p2);
if(p1.y==p2.y&&p1.x>p2.x)swap(p1, p2);
p=p1;
v=p2-p1;
}
//int toLeft(const Vect &V)const { return v.toLeft(V); }
int toLeft(const Point &P)const { return v.toLeft(Vect(p, P)); }
bool is_parallel(const Line &L)const { return v.y*L.v.x==v.x*L.v.y; }
bool is_vertical(const Line &L)const { return v.is_vertical(L.v); }
bool is_intersect(const Segment &S)const
{
return v.toLeft(p-S.st)*v.toLeft(p-S.ed)<=0;
}
bool is_on(const Segment &S)const { return !toLeft(S.st)&&!toLeft(S.ed); }
bool is_on(const Point &A)const { return !toLeft(A); }
pair<bool, Point>get_intersect(const Line &L)const
{
if(is_parallel(L))return make_pair(false, Point());
Vect OQ=Vect(p)+(v*(L.v.cross(Vect(L.p, p))))/(v.cross(L.v));
return make_pair(true, Point(OQ.x, OQ.y));
}
pair<bool, Point>get_intersect(const Segment &S)const
{
if(!is_intersect(S))return make_pair(false, Point());
return get_intersect(Line(S));
}
db dis(const Point &P) const { return abs(v.cross(Vect(P, p)))/v.len(); }
Point project(const Point &A) const
{
Vect Q=Vect(p)+v*((v.dot(A-p))/v.len2());
return Point(Q.x, Q.y);
}
friend ostream &operator<<(ostream &o, const Line &L) { o<<"[ p="<<L.p<<" v="<<L.v<<" ]"; return o; }
};
typedef Line_t<gtype> Line;
/**
* @note store points in anticlockwise order
*/
struct Polygon :vector<Point>
{
using db=gtype;
Polygon() {}
Polygon(int n) :vector<Point>(n) {}
Polygon(const vector<Point> &vec) :vector<Point>(vec) {}
Polygon(const initializer_list<Point> &l) :vector<Point>(l) {}
int nex(const int index)const { return index+1==size()?0:index+1; }
int pre(const int index)const { return index==0?size()-1:index-1; }
Point nextPoint(const int index)const { return at(nex(index)); }
Point prevPoint(const int index)const { return at(pre(index)); }
/**
* @return pair<int,int> [flag, winding number]
* @note flag=1: in, flag=0: on, flag=-1: out
*/
pii is_in(const Point &P)const
{
int cnt=0;
for(int i=0; i<size(); i++)
{
const Point &st=at(i);
const Point &ed=at(nex(i));
if(Segment(st, ed).is_on(P))return make_pair(0, 0);
if(st.y==ed.y)continue;
auto k=(ed-st).cross(P-st);
auto d1=st.y-P.y;
auto d2=ed.y-P.y;
if(k>0&&d1<=0&&d2>0)++cnt;
if(k<0&&d2<=0&&d1>0)--cnt;
}
return make_pair(cnt?1:-1, cnt);
}
/**
* @brief whether P is in *this(*this is a convex)
*
* @param P
* @return true - P is in or on *this; false - P is out
*/
bool isInConvex(const Point &P)const
{
for(int i=0; i<size(); i++)
{
Vect vec(at(i), at(nex(i)));
if(vec.toLeft(P-at(i))<0)
{
return false;
}
}
return true;
}
bool is_convex()const
{
auto xmul=[&](const Point &p1, const Point &p2, const Point &p0)->db
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
};
auto sgn=[&](const db &x)->int
{
if(x>0)return 1;
return x<0?2:0;
};
vector<bool>s(3, true);
for(int i=0; i<size()&&(s[1]|s[2]); i++)
{
int u=i;
int v=nex(u);
int w=nex(v);
s[sgn(xmul(at(v), at(w), at(u)))]=false;
}
return s[1]|s[2];
}
db area()const
{
db ans=0;
for(int i=0; i<size(); i++)
ans+=Vect(at(i)).cross(Vect(at(nex(i))));
return abs(ans/2);
}
db perimeter()const
{
db ans=0;
for(int i=0; i<size(); i++)
ans+=at(i).dis(nextPoint(i));
return ans;
}
};
struct Convex :Polygon
{
Convex() :Polygon() {}
Convex(int n) :Polygon(n) {}
Convex(const vector<Point> &vec) :Polygon(vec) {}
Convex(const initializer_list<Point> &l) :Polygon(l) {}
/**
* @brief check whether Point is in *this convex in O(logn)
*
* @param a the Point
* @return int 1:in 0:on -1:out
*/
int is_in(const Point &a) const
{
const auto &p=*this;
if(p.size()==1) return a==p[0]?0:-1;
if(p.size()==2) return Segment{p[0], p[1]}.is_on(a)?0:-1;
if(a==p[0]) return 0;
if((p[1]-p[0]).toLeft(a-p[0])==-1||(p.back()-p[0]).toLeft(a-p[0])==1) return -1;
const auto cmp=[&](const Point &u, const Point &v)->bool
{
return (u-p[0]).toLeft(v-p[0])==1;
};
const size_t i=lower_bound(p.begin()+1, p.end(), a, cmp)-p.begin();
if(i==1) return Segment{p[0], p[i]}.is_on(a)?0:-1;
if(i==p.size()-1&&Segment{p[0], p[i]}.is_on(a)) return 0;
if(Segment{p[i-1], p[i]}.is_on(a)) return 0;
return (p[i]-p[i-1]).toLeft(a-p[i-1])>0?1:-1;
}
/**
* @brief Andrew O(nlogn)
*
* @param p
* @return Convex Hull
*/
static Convex convexHull(vector<Point> p)
{
vector<Point> st;
if(p.empty()) return Convex(st);
sort(p.begin(), p.end());
const auto check=[](const vector<Point> &st, const Point &u)
{
const auto back1=st.back(), back2=*prev(st.end(), 2);
return (back1-back2).toLeft(u-back1)<=0;
};
for(const Point &u:p)
{
while(st.size()>1&&check(st, u)) st.pop_back();
st.push_back(u);
}
size_t k=st.size();
p.pop_back(); reverse(p.begin(), p.end());
for(const Point &u:p)
{
while(st.size()>k&&check(st, u)) st.pop_back();
st.push_back(u);
}
st.pop_back();
return Convex(st);
}
};
/**
* @brief sort Points by arg (i.e. atan) in anticlockwise
* @note 1: y<0
* @note 2: (x=0, y=0)
* @note 3: (x>0, y=0)
* @note 4: y>0
* @note 5: (x<0, y=0)
* @note Points with the same arg can be ordered arbitrarily
*/
struct argcmp
{
bool operator()(const Point &a, const Point &b)const
{
auto quad=[&](const Point &p)->int
{
if(p.y<0)return 1;
if(p.y>0)return 4;
if(p.x>0)return 3;
if(p.x<0)return 5;
return 2;
};
int qa=quad(a), qb=quad(b);
if(qa!=qb)return qa<qb;
auto t=Vect(a).cross(b);
return t>0;
}
};
}
using namespace geometry;
int main()//MARK: main
{
#ifndef xxx
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
cout<<fixed<<setprecision(10);
int n;
cin>>n;
Polygon poly(n);
for(auto &p:poly)
{
cin>>p;
}
auto checkSame=[&]()->bool
{
map<Point, bool>mp;
for(auto p:poly)
{
if(mp.count(p))
{
return true;
}
mp[p]=true;
}
return false;
};
Convex conv=Convex::convexHull(poly);
cout<<(!checkSame()&&poly.area()==conv.area()?"Yes":"No")<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
4 0 0 0 1 1 1 1 0
output:
Yes
result:
ok answer is YES
Test #3:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 0 0 0 3 1 2 1 1
output:
Yes
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
No
result:
ok answer is NO
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3896kb
input:
5 0 0 1000000000 0 1000000000 500000000 1000000000 1000000000 0 1000000000
output:
Yes
result:
wrong answer expected NO, found YES