QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373233#7730. Convex CheckerdodolaWA 1ms3816kbC++143.2kb2024-04-01 11:46:382024-04-01 11:46:39

Judging History

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

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

answer

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
const ld eps = 1e-18;
const ld pi = acos(-1.0);
/*
符合洛谷题目格式的代码
*/

struct point {
    ld x, y;
    point operator+(const point& p)const {
        return { x + p.x,y + p.y };
    }
    point operator-(const point& p)const {
        return { x - p.x,y - p.y };
    }
    bool operator==(const point& p)const {
        return p.x == x && p.y == y;
    }
    point rotate(ld t)const {
        return { x * cos(t) - y * sin(t), x * sin(t) + y * cos(t) };
    }
    point rot90()const {
        return { -y,x };
    }
};

struct line {
    point s, t;
};

int sgn(ld x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}
ld sqr(ld x) {
    return x * x;
}
ld dis(const point& a, const point& b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

ld dot(const point& a, const point& b) {
    return a.x * b.x + a.y * b.y;
}
ld det(const point& a, const point& b) {
    return a.x * b.y - a.y * b.x;
}
vector<point>Andrew(vector<point>& p) {
    sort(p.begin(), p.end(), [](const point& a, const point& b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
        });
    vector<point> res;
    for (int i = 0; i < p.size(); i++) {    // 下凸壳
        while (res.size() > 1
            && det(res.back() - res[res.size() - 2], p[i] - res[res.size() - 2]) <= 0)
            res.pop_back();
        res.push_back(p[i]);
    }
    int k = res.size();
    for (int i = p.size() - 2; i >= 0; i--) {   // 上凸壳
        while (res.size() > k
            && det(res.back() - res[res.size() - 2], p[i] - res[res.size() - 2]) <= 0)
            res.pop_back();
        res.push_back(p[i]);
    }
    res.pop_back(); // 删除重复的点,即首尾相同
    return res;
}

bool turn_left(const point& a, const point& b, const point& c) {
    return sgn(det(b - a, c - a)) > 0;
}

vector<point> Graham(vector<point>& p) {
    point base = *min_element(p.begin(), p.end(), [](const point& a, const point& b) {
        return a.y == b.y ? a.x < b.x : a.y < b.y;
        });
    sort(p.begin(), p.end(), [&](const point& u, const point& v) {
        int s = sgn(det(u - base, v - base));
        if (s)return s > 0;
        return sgn(dis(u, base) - dis(v, base)) < 0;
        });
    vector<point>res;
    for (auto i : p) {
        while (res.size() > 1
            && !turn_left(res[res.size() - 2], res.back(), i))
            res.pop_back();
        res.push_back(i);
    }
    return res;
}

// 求凸包的周长
ld convex_perimeter(vector<point>& p) {
    ld res = 0;
    for (int i = 0; i < p.size(); i++)
        res += dis(p[i], p[(i + 1) % p.size()]);
    return res;
}

bool convex_checker(vector<point>& p) {
    vector<point> res = Andrew(p);
    return res.size() == p.size();
}

void solve() {
    ll n;cin >> n;
    vector<point> p(n);
    for (ll i = 0;i < n;i++) {
        cin >> p[i].x >> p[i].y;
    }
    if (convex_checker(p)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

int main() {
    solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 3724kb

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

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3812kb

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES