QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312678#7730. Convex CheckerEndPBWA 3ms16164kbC++172.5kb2024-01-24 10:37:542024-01-24 10:37:54

Judging History

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

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

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];

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;
}

int main() {//Andrew 169ms
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) p[i].in();
    tp = Andrew(p, n, stk);
    if (tp == n) {
        for (int i = 1; i < n; ++i)
            if (!(p[i + 1] - p[i] == stk[i + 1] - stk[i])) {
                cout << "No";
                return 0;
            }
        cout << "Yes";
    } else cout << "No";
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 16164kb

input:

3
0 0
1 0
0 1

output:

No

result:

wrong answer expected YES, found NO