QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#242313#7730. Convex CheckerinvadedWA 1ms3580kbC++174.6kb2023-11-07 09:51:382023-11-07 09:51:40

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2023-11-07 09:51:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3580kb
  • [2023-11-07 09:51:38]
  • 提交

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;
struct Point
{
	ll x, y;
	void read()
	{
		cin>>x>>y;
	}
	bool operator<(const Point &p)const
	{
		return x==p.x?y<p.y:x<p.x;
	}
	bool operator==(const Point &p)const
	{
		return x==p.x&&y==p.y;
	}
	friend ostream &operator<<(ostream &o, const Point &p)
	{
		o<<'('<<p.x<<','<<p.y<<')';
		return o;
	}
};
struct Vect
{
	ll x, y;
	Vect() :x(0), y(0) {}
	Vect(Point st, Point ed) :x(ed.x-st.x), y(ed.y-st.y) {}
	ll dot(Vect V)
	{
		return x*V.x+y*V.y;
	}
	ll cross(Vect V)
	{
		return x*V.y-y*V.x;
	}
	ll toLeft(Vect V)
	{
		ll t=cross(V);
		return (t>0)-(t<0);
	}
};
Vect operator-(Point ed, Point st)
{
	return Vect(st, ed);
}
vector<Point> convexHull1(vector<Point> p)
{
	vector<Point> st;
	if(p.empty()) return 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 st;
}
vector<Point> convexHull2(vector<Point> p)
{
	vector<Point> st;
	if(p.empty()) return st;
	sort(p.begin(), p.end());
	reverse(p);
	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 st;
}
bool preCheck(const vector<Point> &poly)
{
	int n=poly.size();
	for(int i=0; i<n; i++)
	{
		int u=i;
		int v=(i+1)%n;
		int w=(i+2)%n;
		Vect v1(poly[u], poly[v]);
		Vect v2(poly[v], poly[w]);
		if(v1.toLeft(v2)==0)
		{
			return false;
		}
	}
	return true;
}
bool compare(const vector<Point> &poly, const vector<Point> &convex)
{
	if(poly.size()!=convex.size())return false;
	int n=poly.size();
	int it=find(poly.begin(), poly.end(), convex.front())-poly.begin();
	if(it==poly.size())return false;
	auto check1=[&]()->bool
	{
		for(int i=(it+1)%n, j=1%n; i!=it; i=(i+1)%n, j=(j+1)%n)
		{
			if(poly[i]==convex[j])
			{
				continue;
			}
			else
			{
				return false;
			}
		}
	};
	auto check2=[&]()->bool
	{
		for(int i=(it-1+n)%n, j=n-1; i!=it; i=(i-1+n)%n, j=(j-1+n)%n)
		{
			if(poly[i]==convex[j])
			{
				continue;
			}
			else
			{
				return false;
			}
		}
	};
	return true;
}
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;
	vector<Point>poly(n);
	for(int i=1; i<=n; i++)
	{
		poly[i-1].read();
	}
	auto convex1=convexHull1(poly);
	auto convex2=convexHull2(poly);
	//dbg(convex1);
	//dbg(convex2);
	bool flag=preCheck(poly)&&(compare(poly, convex1)||compare(poly, convex2));
	cout<<(flag?"Yes":"No")<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 3580kb

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

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

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

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES