QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#594103#7906. Almost ConvexssxTL 0ms4016kbC++142.9kb2024-09-27 19:13:152024-09-27 19:13:16

Judging History

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

  • [2024-09-27 19:13:16]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4016kb
  • [2024-09-27 19:13:15]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ll int
#define pll pair<ll, ll>
const int N = 2e3 + 50;
const double eps = 1e-8;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}


inline int sgn(double x)
{
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

struct Point 
{
    double x, y;
    ll id;
    Point (){};
    Point (double x, double y) : x(x), y(y){}

    Point operator + (Point B) {return Point(x + B.x, y + B.y);}
    Point operator - (Point B) {return Point(x - B.x, y - B.y);}
    Point operator * (double k) {return Point(x * k, y * k);}
    Point operator / (double k) {return Point(x / k, y / k);}
    bool operator == (Point B) {return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
    bool operator < (Point B) const
    {
        return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);
    }
};

typedef Point Vector;
inline double Cross (Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
inline double Distance (Point &A, Point &B) {return hypot(A.x - B.x, A.y - B.y);}

Point p[N];

inline int Convex_hull(int n, Point *ch)
{
    sort(p, p + n);
    int v = 0;
    for (int i = 0; i < n; i++)
    {
        while (v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) v --;
        ch[v ++] = p[i];
    }
    int j = v;
    for (int i = n - 2; i >= 0; i--)
    {
        while (v > j && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) v --;
        ch[v ++] = p[i];
    }
    if (n > 1) v --;
    return v;
}

inline double ang(Point &a)
{
    return atan2(a.x, a.y);
}

bool cmp(Point &a, Point &b) 
{
    double angle1 = ang(a);
    double angle2 = ang(b);
    return angle1 < angle2;
}

Point ch[N], d[N];
ll st[N];

void solve()
{
    ll n, ans = 0;
    n = read();
    for (int i = 0; i < n; i++) 
    {
        p[i].x = read();
        p[i].y = read();
        p[i].id = i;
    }
    int R = Convex_hull(n, ch);
    for (int i = 0; i < R; i++) st[ch[i].id] = 1;
    Point p0;
    ll cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cnt = 0;
        if (st[p[i].id] == 1) continue;
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
            p0 = p[j] - p[i];
            p0.id = p[j].id;
            d[++ cnt] = p0;
        }
        sort(d + 1, d + cnt + 1, cmp);
        for (int j = 1; j < cnt; j++)
        {   
            if (st[d[j].id] == 1 && st[d[j + 1].id] == 1) ans ++;
        }
        if (st[d[cnt].id] == 1 && st[d[0].id] == 1) ans ++;
    }
    cout << ans + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll T = 1;
    //cin >> T;
    while (T --) 
    {
        solve();
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: