QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474764 | #7730. Convex Checker | qwqpmp | WA | 0ms | 3796kb | C++14 | 8.2kb | 2024-07-12 23:51:45 | 2024-07-12 23:51:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define inf (0x3f3f3f3f)
#define linf (0x3f3f3f3f3f3f3f3fLL)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
typedef long double db;
mt19937 mrand(random_device{}());
const ll mod=1e9+7;
int rnd(int x) { return mrand()%x; }
inline ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res; }
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
//head
namespace Geo {
using T=db; // 还是不要乱动免得精度爆炸
constexpr T EPS=1e-10;
constexpr T INF=1e20;
constexpr T PI=acos(-1.0); // 180
inline int sign(T a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(T a, T b) { return sign(a-b); }
inline T pow2(T x) { return x*x; }
struct P {
T x, y;
P(T _x=0, T _y=0) : x(_x), y(_y) {}
void read() {
int _x,_y;
cin>>_x>>_y;
x=_x,y=_y;
}
P operator+() { return *this; }
P operator-() { return P(-x,-y); }
P operator+(P p) { return P(x + p.x, y + p.y); }
P operator-(P p) { return P(x - p.x, y - p.y); }
P operator*(T k) { return P(x * k, y * k); }
P operator/(T k) { return P(x / k, y / k); }
bool operator<(P p) const {
int c = cmp(x, p.x);
if (c) return c == -1;
return cmp(y, p.y) == -1;
}
// (a == b and b == c) != (a == c)
bool operator==(P &p) { return cmp(p.x,x) == 0 and cmp(p.y,y) == 0; }
T dot(P p) { return x * p.x + y * p.y; }
T det(P p) { return x * p.y - y * p.x; } // an = this->p
T abs2() { return x * x + y * y; }
T abs() { return sqrt(abs2()); }
T distTo(P p) { return (*this - p).abs(); } // distanct(this,p)
P rot90() { return P(-y,x); } // 逆时针
P unit() { return *this/abs(); }
P rot(T an){ return {x*cos(an)-y*sin(an),x*sin(an)+y*cos(an)}; } // 顺时针
// quad [0,pi)-1, [pi,2pi)-0.
// 判断是在 x 轴上半段还是下半段
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
T alpha() { return atan2(y, x); } // atan2l-(long double)
T angle(P p) { return acos(((*this).dot(p))/abs()/p.abs()); }
};
ostream &operator<<(ostream &os,const P &p) {
return os << p.x << " " << p.y;
}
// istream &operator>>(istream &is,P &p) {
// is >> p.x >> p.y;
// return is;
// }
// crossOp==0 三点共线 crossOp==1/-1 p3 在 p2 逆/顺时针
// crossOp 在 10-9 处可能会出现一定的精度问题
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
bool chkLL(P p1, P p2, P q1, P q2) { // 两条 直线 是否相交
T a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return sign(a1+a2) != 0;
}
P isLL(P p1, P p2, P q1, P q2) { // 求 直线 交点
T a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
bool intersect(T l1,T r1,T l2,T r2) { // 判断 [l1,r1] 与 [l2,r2] 是否相交
if(l1>r1) swap(l1,r1); if(l2>r2) swap(l2,r2);
return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}
bool isSS(P p1, P p2, P q1, P q2) { // 线段相交
return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) &&
crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) <= 0;
}
bool isSS_strict(P p1, P p2, P q1, P q2) { // 线段严格相交 不能交端点
return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) < 0;
}
bool isMiddle(T a, T m, T b) {
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b) { // 判断一个点是否在平面中间
return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
bool onSeg(P p1, P p2, P q) { // 判断 点 q 是不是在线段 p1p2 上
return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
bool onSeg_strict(P p1, P p2, P q) {
return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
P proj(P p1, P p2, P q) { // 求 q 到 直线p1p2 的投影 (垂足), p1 != p2!
P dir = p2 - p1;
return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
P reflect(P p1, P p2, P q) { // 求 q 以 直线p1p2 为轴的反射, p1 != p2!
return proj(p1,p2,q) * 2 - q;
}
T nearest(P p1,P p2,P q){ // 求 q 到 线段 p1p2 的最小距离
if (p1==p2) return p1.distTo(q);
P h = proj(p1,p2,q);
if(isMiddle(p1,h,p2))
return q.distTo(h);
return min(p1.distTo(q),p2.distTo(q));
}
T disSS(P p1, P p2, P q1, P q2) { // 求 线段 p1p2 与 线段 q1q2 的距离
if(isSS(p1,p2,q1,q2)) return 0;
return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
T area(vector<P> ps){ // 求 简单多边形 的面积
T ret = 0; rep(i,0,ps.size()) ret += (ps[i]-ps[0]).det(ps[(i+1)%ps.size()]-ps[0]);
return ret/2;
}
int contain(const vector<P> &ps, P p) { // 判断 点 在不在一个 简单多边形 里面
//2:inside,1:on_seg,0:outside
int n = ps.size(), ret = 0;
rep(i,0,n) {
P u=ps[i],v=ps[(i+1)%n];
if(onSeg(u,v,p)) return 1;
if(cmp(u.y,v.y)<=0) swap(u,v);
if(cmp(p.y,u.y) >0 || cmp(p.y,v.y) <= 0) continue;
ret ^= crossOp(p,u,v) > 0;
}
return ret*2;
}
vector<P> convexHull(vector<P> ps) { // 严格凸包
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++]) // 求下凸包
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--]) // 求上凸包
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
qs.resize(k - 1);
return qs;
}
vector<P> convexHullNonStrict(vector<P> ps) { // 不严格凸包
//caution: need to unique the Ps first
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
qs.resize(k - 1);
return qs;
}
T convexDiameter(vector<P> ps) { // 旋转卡壳
int n = ps.size(); if(n <= 1) return 0;
int is = 0, js = 0;
rep(k,1,n) is=ps[k]<ps[is]?k:is,js=ps[js]<ps[k]?k:js;
int i = is, j = js;
T ret = ps[i].distTo(ps[j]);
do{
if((ps[(i+1)%n]-ps[i]).det(ps[(j+1)%n]-ps[j]) >= 0)
(++j)%=n;
else
(++i)%=n;
ret = max(ret,ps[i].distTo(ps[j]));
}while(i!=is || j!=js);
return ret;
}
// 替代半平面交 求一条直线切割多边形生成的新多边形
vector<P> convexCut(const vector<P>&ps, P q1, P q2) {
// 比较暴力, 时间复杂度有点寄
vector<P> qs;
int n = ps.size();
rep(i,0,n){
P p1 = ps[i], p2 = ps[(i+1)%n];
int d1 = crossOp(q1,q2,p1), d2 = crossOp(q1,q2,p2);
if(d1 >= 0) qs.pb(p1); // 在直线q1q2左边
if(d1 * d2 < 0) qs.pb(isLL(p1,p2,q1,q2));
}
return qs;
}
T rad(P p1,P p2) { // 两个向量极角相减
return atan2l(p1.det(p2),p1.dot(p2));
}
}
using namespace Geo;
int n;
vector<P> ps;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
bool ok=1;
cin>>n;
ps.resize(n);
rep(i,0,n) ps[i].read();
map<P,int> ls;
for (int i=0;i<n;i++) {
if (ls[ps[i]]) ok=0;
ls[ps[i]]++;
}
if (!ok) {
cout<<"No"<<endl;
return 0;
}
auto r=convexHull(ps);
db qwq=area(ps);
db pmp=area(r);
// cout<<qwq<<endl;
// cout<<pmp<<endl;
if (abs(qwq)==abs(pmp)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
//Shu daisuki
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
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: 3724kb
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: 3640kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: 0
Accepted
time: 0ms
memory: 3636kb
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: 3796kb
input:
5 0 0 1000000000 0 1000000000 500000000 1000000000 1000000000 0 1000000000
output:
Yes
result:
wrong answer expected NO, found YES