QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#312709#7730. Convex CheckerEndPBWA 12ms34992kbC++172.9kb2024-01-24 11:00:202024-01-24 11:00:20

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-01-24 11:00:20]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:34992kb
  • [2024-01-24 11:00:20]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
#define ll long double
#define ld ll
#define Vector Point
#define S(x) (x)*(x)
#define N 200010

const int Kep = 1;
const ld eps = 1e-8, pi = acosl(-1.0), Mn = powl(10.0, -Kep);

inline int sign(ld a) { return a < -eps ? -1 : (a > eps ? 1 : 0); }

inline ld Abs(ld a) { return a * sign(a); }//取绝对值
inline void Out(ld a, int k = Kep) {
    if (-Mn < a && a < Mn) a = 0;
    cout << fixed << setprecision(Kep) << a;//<iomanip>
}

struct Point {
    ld x, y;

    Point(ld a = 0, ld b = 0) { x = a, y = b; }

    inline void in() { cin >> x >> y; }

    inline void out() {
        Out(x);
        cout << " ";
        Out(y);
        cout << endl;
    }
};

inline ld Dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }//【点积】
inline ld Cro(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }//【叉积】
inline ld Len(Vector a) { return sqrtl(Dot(a, a)); }//【模长】
inline ld Angle(Vector a, Vector b) { return acosl(Dot(a, b) / Len(a) / Len(b)); }//【两向量夹角】
inline Vector Normal(Vector a) { return Vector(-a.y, a.x); }//【法向量】
inline Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }

inline Vector operator-(Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }

inline Vector operator*(Vector a, ld b) { return Vector(a.x * b, a.y * b); }

inline bool operator==(Point a, Point b) { return !sign(a.x - b.x) && !sign(a.y - b.y); }//两点坐标重合则相等

Point stk[N];
int tp = 0;
Point p[N], tmp[N];

bool cmpb(Point a, Point b) {
    return Abs(a.x - b.x) < eps ? a.y < b.y : a.x < b.x;
}

inline int Andrew(Point *p, int n, Point *stk) {//点的存储位置[1,n]
    sort(p + 1, p + 1 + n, cmpb);
    int tp = 0;
    for (int i = 1; i <= n; ++i) {
        while (tp > 1 && sign(Cro(stk[tp] - stk[tp - 1], p[i] - stk[tp - 1])) <= 0) --tp;
        stk[++tp] = p[i];
    }
    int k = tp;
    for (int i = n - 1; i >= 1; --i) {
        while (tp > k && sign(Cro(stk[tp] - stk[tp - 1], p[i] - stk[tp - 1])) <= 0) --tp;
        stk[++tp] = p[i];
    }
    return --tp;
}

inline int nxt(int x, int n) {
    return x == n ? 1 : x + 1;
}
Point ord_p[N], ord_stk[N];
int main() {//Andrew 169ms
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) p[i].in(), tmp[i] = p[i];
    tp = Andrew(tmp, n, stk);
//    for (int i = 1; i <= tp; ++i) stk[i].out();
    if (tp == n) {
        for (int i = 1; i <= n; ++i) {
            ord_p[i] = p[nxt(i, n)] - p[i];
            ord_stk[i] = stk[nxt(i, n)] - stk[i];
        }
        sort(ord_p + 1, ord_p + n + 1, cmpb);
        sort(ord_stk + 1, ord_stk + n + 1, cmpb);
        for (int i = 1; i <= n; ++i) {
            if (!(ord_p[i] == ord_stk[i])) {
                cout << "No";
                return 0;
            }
        }
        cout << "Yes";
    } else cout << "No";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 34992kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 12ms
memory: 34972kb

input:

4
0 0
0 1
1 1
1 0

output:

Yes

result:

ok answer is YES

Test #3:

score: -100
Wrong Answer
time: 8ms
memory: 34904kb

input:

4
0 0
0 3
1 2
1 1

output:

No

result:

wrong answer expected YES, found NO