QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241981#7730. Convex CheckerinvadedWA 0ms3684kbC++1712.8kb2023-11-06 20:41:022023-11-06 20:41:03

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2023-11-06 20:41:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3684kb
  • [2023-11-06 20:41:02]
  • 提交

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>
	{
		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;
	}
	Convex conv=Convex::convexHull(poly);
	cout<<(conv.size()==n?"Yes":"No")<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3624kb

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: 3684kb

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: 3656kb

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3652kb

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES