QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474733#7730. Convex CheckerqwqpmpWA 0ms3776kbC++1412.6kb2024-07-12 23:03:002024-07-12 23:03:00

Judging History

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

  • [2024-07-12 23:03:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3776kb
  • [2024-07-12 23:03:00]
  • 提交

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].det(ps[(i+1)%ps.size()]); 
    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 checkconvex(const vector<P>&ps) {
    vector<P> q; q=convexHull(ps);
    //printf("???? %d %d\n",SZ(q),SZ(ps));
    //assert(SZ(ps)>=SZ(q));
    for (auto x:ps) if (contain(q,x)==2) return -1;
    return area(q);
}
T min_dist(vector<P> &ps,int l,int r) { //平面最近点对,[l,r),要求ps按x升序
    if (r-l<=5) {
        T ret=1e18;
        for(int i=l;i<r;++i) for(int j=l;j<i;++j) {    
            ret=min(ret,ps[i].distTo(ps[j]));
        }
        return ret;
    }
    int m=(l+r)>>1;
    db ret=min(min_dist(ps,l,m),min_dist(ps,m,r));
    vector<P> qs;
    for(int i=l;i<r;++i)
        if (abs(ps[i].x - ps[m].x) <= ret)
            qs.push_back(ps[i]);
    sort(qs.begin(), qs.end(), [](P a, P b) -> bool
         { return a.y < b.y; });
    for(int i=1;i<qs.size();++i) 
        for (int j=i-1;j>=0&&qs[j].y>=qs[i].y-ret;--j)
            ret = min(ret, qs[i].distTo(qs[j]));
    return ret;
}
int type(P o1, T r1, P o2, T r2) {
    // 4 相离 3 外切 2 相交 1 内切 0 包含
    T d = o1.distTo(o2);
    if (cmp(d, r1 + r2) == 1)
        return 4;
    if (cmp(d, r1 + r2) == 0)
        return 3;
    if (cmp(d, abs(r1 - r2)) == 1)
        return 2;
    if (cmp(d, abs(r1 - r2)) == 0)
        return 1;
    return 0;
}
vector<P> isCL(P o, T r, P p1, P p2) { // 圆和线相交 的 两个交点
    if (cmp(abs((o-p1).det(p2-p1)/p1.distTo(p2)),r)>0) return {};
    T x=(p1-o).dot(p2-p1),y=(p2-p1).abs2(),d=x*x-y*((p1-o).abs2()-r*r);
    d=max(d,(T)0.0); P m=p1-(p2-p1)*(x/y),dr=(p2-p1)*(sqrt(d)/y);
    return {m-dr,m+dr}; // along dir: p1->p2
}
vector<P> isCC(P o1, T r1, P o2, T r2) { // 圆与圆相交 的 两个交点 
    // need to check whether two circles are the same
    T d=o1.distTo(o2);
    if (cmp(d,r1+r2)==1) return {};
    if (cmp(d,abs(r1-r2))==-1) return {};
    d=min(d,r1+r2);
    T y=(r1*r1+d*d-r2*r2)/(2*d),x=sqrt(r1*r1-y*y);
    P dr=(o2-o1).unit(); P q1=o1+dr*y,q2=dr.rot90()*x;
    return {q1-q2,q1+q2}; // along circle 1
    // 在第一个圆的逆时针方向上
}

// 外公切线 extanCC : r2 
// 内公切线 intanCC : -r2
// 点到圆的切线 tanCP : r2 = 0
vector<pair<P,P>> tanCC(P o1,T r1,P o2,T r2) {
    // tanCP pair<P,P> P1 = CP, P2 = o2;
    P d=o2-o1;
    T dr=r1-r2,d2=d.abs2(),h2=d2-dr*dr;
    if (sign(d2)==0 or sign(h2)<0) return {};
    h2=max((T)(0.0),h2);
    vector<pair<P,P>> ret;
    for (T sign : {-1,1}) {
        P v=(d*dr+d.rot90()*sqrt(h2)*sign)/d2;
        ret.pb({o1+v*r1,o2+v*r2});
    }
    if (sign(h2)==0) ret.pop_back();
    return ret;
}
P inCenter(P A, P B, P C) { //内心,角平分线的交点
    T a = (B - C).abs(), b = (C - A).abs(), c = (A - B).abs();
    return (A * a + B * b + C * c) / (a + b + c);
}
P circumCenter(P a, P b, P c) { //外心,垂直平分线的交点
    P bb = b - a, cc = c - a;
    T qq = bb.abs2(), dc = cc.abs2(), d = 2 * bb.det(cc);
    return a - P(bb.y * dc - cc.y * qq, cc.x * qq - bb.x * dc) / d;
}
P orthoCenter(P a, P b, P c) { //垂心,垂线的交点
    P ba = b - a, ca = c - a, bc = b - c;
    T Y = ba.y * ca.y * bc.y,
           A = ca.x * ba.y - ba.x * ca.y,
           x0 = (Y + ca.x * ba.y * b.x - ba.x * ca.y * c.x) / A,
           y0 = -ba.x * (x0 - c.x) / ba.y + ca.y;
    return {x0, y0};
}
pair<P,T> min_circle(vector<P> ps) { // 最小圆覆盖 O(n)
    random_shuffle(ps.begin(),ps.end());
    int n=ps.size();
    P o=ps[0]; T r=0;
    rep(i,1,n) if (o.distTo(ps[i])>r+EPS) {
        o=ps[i],r=0;
        rep(j,0,i) if (o.distTo(ps[j])>r+EPS) {
            o=(ps[i]+ps[j])/2; r=o.distTo(ps[i]);
            rep(k,0,j) if (o.distTo(ps[k])>r+EPS) {
                o=circumCenter(ps[i],ps[j],ps[k]); 
                r=o.distTo(ps[i]);
            }
        }
    }
    return {o,r};
}
T rad(P p1,P p2) { // 两个向量极角相减
    return atan2l(p1.det(p2),p1.dot(p2));
}
T incircle(P p1, P p2, P p3) {
    T A = p1.distTo(p2);
    T B = p2.distTo(p3);
    T C = p3.distTo(p1);
    return sqrtl(A*B*C/(A+B+C));
}
T areaCT(T r, P p1, P p2) { // 求 三角形 (0,0) p1,p2 与 (0,0),r 为圆心半径的交面积
    vector<P> is=isCL(P(0,0),r,p1,p2);
    if (is.empty()) return r*r*rad(p1,p2)/2;
    bool b1=cmp(p1.abs2(),r*r)==1,b2=cmp(p2.abs2(),r*r)==1;
    if (b1&&b2) {
        if (sign((p1-is[0]).dot(p2-is[0]))<=0&&sign((p1-is[1]).dot(p2-is[1]))<=0)
            return r*r*(rad(p1,is[0])+rad(is[1],p2))/2+is[0].det(is[1])/2;
        else return r*r*rad(p1,p2)/2;
    }
    if (b1) return (r*r*rad(p1,is[0])+is[0].det(p2))/2;
    if (b2) return (p1.det(is[1])+r*r*rad(is[1],p2))/2;
    return p1.det(p2)/2;
}
}
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]]++;
    }
	
	for (int i=0;i<n;i++) {
		P p1=ps[i],p2=ps[(i+1)%n],p3=ps[(i+2)%n];
		P f1=p2-p1,f2=p2-p3;
		if (abs(rad(f1,f2))>=PI) ok=0;
	}    
	if (ok) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
//Shu daisuki

详细

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

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

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

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

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

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES