QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#312769#7730. Convex Checkertiny_fishWA 0ms4368kbC++172.0kb2024-01-24 11:49:482024-01-24 11:49:49

Judging History

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

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

answer

#include <cstdio>
#include <cmath>
#include <algorithm>

const int maxn = 2e5 + 5;

typedef double ld;

struct Point{
    ld x, y, ang;
    int id;
    Point operator - (const Point &oth) const { return {x - oth.x, y - oth.y}; }
    bool operator == (const Point &oth) const { return x == oth.x && y == oth.y; }
} p[maxn];

ld dis(const Point &a, const Point &b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

ld det(const Point &a, const Point &b){
    return a.x * b.y - a.y * b.x; 
}

int n, sta[maxn], top;

double ans;

bool checkR(int p){
    for(int i = 1; i <= n; i++){
        if(sta[p] ^ i) return false;
        p = p < n ? p+1 : 1;
    }
    return true;
}

bool checkL(int p){
    for(int i = 1; i <= n; i++){
        if(sta[p] ^ i) return false;
        p = p > 1 ? p-1 : n;
    }
    return true;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf%lf", &p[i].x, &p[i].y);
        p[i].id = i;
    }
    for(int i = 2; i <= n; i++){
        if(p[i].y < p[1].y || (p[i].y == p[1].y && p[i].x < p[1].x)) std::swap(p[1], p[i]);
    }
    for(int i = 2; i <= n; i++){
        p[i].ang = atan2(p[i].y - p[1].y, p[i].x - p[1].x);
    }
    std::sort(p+2, p+1+n, [&](Point a, Point b){ return a.ang == b.ang ? dis(a, p[1]) < dis(b, p[1]) : a.ang < b.ang; });
    int T = std::unique(p+1, p+1+n) - p - 1; if(T < 3){ puts("No"); return 0; }
    sta[++top] = 1;
    for(int i = 2; i <= n; i++){
        while(top >= 2 && det(p[sta[top]] - p[sta[top-1]], p[i] - p[sta[top]]) < 0){
            top--;
        }
        sta[++top] = i;
    }
    if(top < T){ puts("No"); return 0; }
    for(int i = 1; i <= top; i++) sta[i] = p[sta[i]].id;
    int p = std::find(sta+1, sta+1+T, 1) - sta;
    puts((checkL(p) || checkR(p)) ? "Yes" : "No");
    // auto [mn, mx] = std::minmax_element(sta+1, sta+1+top);
    // printf("%d %d\n", mn-sta, mx-sta);
    // for(int i = 1; i <= top; i++) printf("%d%c", sta[i], " \n"[i==top]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

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

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

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

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

input:

5
1 0
4 1
0 1
2 0
3 2

output:

No

result:

ok answer is NO

Test #6:

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

input:

5
0 0
1000000000 0
1000000000 500000000
1000000000 1000000000
0 1000000000

output:

Yes

result:

wrong answer expected NO, found YES