QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312665#7730. Convex CheckerEndPBWA 0ms16288kbC++172.3kb2024-01-24 10:14:592024-01-24 10:14:59

Judging History

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

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

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) cout << "Yes";
    else cout << "No";
}

詳細信息

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

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

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

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

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

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES