QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277254#7906. Almost Convexwenjing233#WA 421ms3844kbC++145.1kb2023-12-06 17:03:432023-12-06 17:03:43

Judging History

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

  • [2023-12-06 17:03:43]
  • 评测
  • 测评结果:WA
  • 用时:421ms
  • 内存:3844kb
  • [2023-12-06 17:03:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int N = 2e3 + 10;
inline int sgn(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1; else return 1;
}
inline int read() {
    int x = 0, k = 1; char ch = getchar();
    for (; ch < 48 || ch > 57; ch = getchar()) k ^= (ch == '-');
    for (; ch >= 48 && ch <= 57; ch = getchar()) x = x * 10 + (ch ^ 48);
    return k ? x : -x;
}
struct Point {
    double x, y;
    int id;
    Point() {}
    Point(double _x, double _y) {
        x = _x, y = _y;
    }
    double distance(Point p) {
        return hypot(x - p.x, y - p.y);
    }
    Point operator -(const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
    double operator ^(const Point &b) const {
        return x * b.y - y * b.x;
    }
    bool operator <(Point b) const {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
    }
    bool operator ==(Point b) const {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
} P[N], P1[N],PP;
int get(Point a){
    if (sgn(a.y)==0){
        if (sgn(a.x)==1) return 0;
        else return 4;
    }
    if (sgn(a.x)==0){
        if (sgn(a.y)==1) return 2;
        else return 6;
    }
    if (sgn(a.x)==1){
        if (sgn(a.y)==1) return 1;
        return 7;
    }
    if (sgn(a.y)==1) return 3;
    return 5;
}
bool Cmp(const Point &aa, const Point &bb){
    Point a=aa-PP,b=bb-PP;
    int f1=get(aa);
    int f2=get(bb);
    if (f1!=f2) return f1<f2;
    return a.y*b.x<b.y*a.x;
    // int f1=a.y>0 || a.y==0 && a.x>0;
    // int f2=b.y>0 || b.y==0 && b.x>0;
    // if (f1!=f2) return f1>f2;
    // return (a^b)>0;
    // return atan((a-PP).y/(a-PP).x)<atan((b-PP).y/(b-PP).x);
    // Point a = aa, b = bb;
    // int d = sgn((a - PP) ^ (b - PP));
    // if (d == 0) {
    //     return sgn(a.distance(PP) - b.distance(PP)) < 0;
    // }
    // return d > 0;
}

// struct cmp {
//     Point p;
//     cmp(const Point &p0) {p = p0;}
//     bool operator() (const Point &aa, const Point &bb) {
//         Point a = aa, b = bb;
//         int d = sgn((a - p) ^ (b - p));
//         if (d == 0) {
//             return sgn(a.distance(p) - b.distance(p)) < 0;
//         }
//         return d > 0;
//     }
// } ;
bool flag[N];
struct polygon{
    int n;
    Point p[N];
    struct cmp {
        Point p;
        cmp(const Point &p0) {p = p0;}
        bool operator() (const Point &aa, const Point &bb) {
            Point a = aa, b = bb;
            int d = sgn((a - p) ^ (b - p));
            if (d == 0) {
                return sgn(a.distance(p) - b.distance(p)) < 0;
            }
            return d > 0;
        }
    } ;
    void norm() {
        Point mi = p[0];
        for (int i = 1; i < n; i++) mi = min(mi, p[i]);
        sort(p, p + n, cmp(mi));
        // cout << n << endl;
        // for (int i = 0; i < n; i++)
        //     printf("%d %d %d\n", p[i].x, p[i].y, p[i].id);
        for (int i = 0; i < n; i++) flag[p[i].id] = 1;
        // cout << endl;
    }
    void getconvex(polygon &convex) {
        sort(p, p + n);
        for (int i = 0; i < min(n, 2); i++)
            convex.p[i] = p[i];
        if (convex.n == 2 && (convex.p[0] == convex.p[1]))
            convex.n--;
        if (n <= 2) return;
        int &top = convex.n;
        top = 1;
        for (int i = 2; i < n; i++) {
            while (top && sgn((convex.p[top] - p[i]) ^ (convex.p[top - 1] - p[i])) <= 0) top--;
            convex.p[++top] = p[i];
        }
        int temp = top;
        convex.p[++top] = p[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            while (top != temp && sgn((convex.p[top] - p[i]) ^ (convex.p[top - 1] - p[i])) <= 0) top--;
            convex.p[++top] = p[i];
        }
        if (convex.n == 2 && (convex.p[0] == convex.p[1]))  
            convex.n--;
        convex.norm();
    }
} poly, poly1;
int n;
int main() {
    n = read();
    for (int i = 0; i < n; i++) {
        P[i].x = read(), P[i].y = read(), P[i].id = i;
        poly.p[i] = P[i];
    }
    poly.n = n;
    poly.getconvex(poly1);
    int sum = 0;
    // for (int j = 0; j < n; j++)
    //     printf("%d ", flag[j]);
    for (int i = 0; i < n; i++) {
        if (flag[P[i].id] == 1) continue;
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (j != i) P1[cnt++] = P[j];
        }
        PP=P[i];
        sort(P1, P1 + n - 1,Cmp);
        // if (i == 3) {
            // cout << PP.x << " " << PP.y << endl;
            // for (int j = 0; j < n - 1; j++)
                // cout << P1[j].x << " " << P1[j].y << " " << P1[j].id << endl;
        // }
        // cout << endl;
        for (int j = 1; j < n - 1; j++)
            if (flag[P1[j].id] == 1 && flag[P1[j - 1].id] == 1) {
                sum++;
                // cout << P1[j].id << " " << P1[j - 1].id << endl;
            }
        if (flag[P1[0].id] == 1 && flag[P1[n - 2].id] == 1) {
            sum++;
            // cout << P1[0].id << " " << P1[n - 2].id << endl;
        }
        // printf("%d %d\n", i, sum);
    }
    printf("%d\n", sum + 1);
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 421ms
memory: 3844kb

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:

924

result:

wrong answer 1st numbers differ - expected: '718', found: '924'