QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#608752#7906. Almost ConvexDoubeecatTL 0ms3960kbC++202.8kb2024-10-04 02:28:032024-10-04 02:28:03

Judging History

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

  • [2024-10-04 02:28:03]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3960kb
  • [2024-10-04 02:28:03]
  • 提交

answer

/*
Undo the destiny.
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    int v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

const ll mod = 998244353;
const double eps = 1e-10;
const int N = 2e3 + 10;
int dcmp(double a) {return a < -eps ? -1 : (a > eps ? 1 : 0);}
struct point {
    double x,y;point(double X = 0,double Y = 0) {x = X,y = Y;}
    friend point operator - (const point &a,const point &b) {
        point c;
        c.x = a.x - b.x;
        c.y = a.y - b.y;
        return c;
    } 
    friend double operator ^ (const point &a,const point &b) {
        return a.x * b.y - a.y * b.x;
    } 
}p[N],O;

bool cmp1(point a,point b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

int convexhull(point *P,int n,int *cp) {
    sort(P+1,P+n+1,cmp1);
    int t = 0;
    for (int i = 1;i <= n;++i) {
        while (t > 1 && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
        cp[++t] = i;
    }
    int st = t;
    for (int i =n-1;i >= 1;--i) {
        while (t > st && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
        cp[++t] = i;
    }
    return --t;
}

int n,cp[N];
bool vis[N];
double theta(point a) {return atan2(a.y,a.x);}
bool lt(double a, double b) { return a - b < -eps; }     // <
void psort(vector <int> &ps, point c)              // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return lt(theta(p[p1] - c), theta(p[p2] - c));
    });
}
signed main() {
    read(n);
    for (int i = 1;i <= n;++i) read(p[i].x,p[i].y);
    int siz = convexhull(p,n,cp);
    /*
    for (int i = 1;i <= siz;++i) {
        cout << p[cp[i]].x << " " << p[cp[i]].y << endl;
    }
    */
    for (int i = 1;i <= siz;++i) vis[cp[i]] = 1;
    ll ans = 1;
    for (int x = 1;x <= n;++x) {
        if (vis[x]) continue;
        vector <int> qwq;
        for (int i = 1;i <= n;++i) {
            if (i != x) qwq.push_back(i);
        }
        psort(qwq,p[x]);
        int sz = qwq.size();
        if (vis[qwq[0]] && vis[qwq[sz-1]])++ans;
        for (int i = 1;i < sz;++i) {
            if (vis[qwq[i]] && vis[qwq[i-1]])++ans;
        }
    }
    cout <<ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 0ms
memory: 3608kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 0ms
memory: 3488kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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:


result: