QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#364561#7906. Almost ConvexZhou_JKTL 1ms4044kbC++232.6kb2024-03-24 15:18:142024-03-24 15:18:14

Judging History

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

  • [2024-03-24 15:18:14]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4044kb
  • [2024-03-24 15:18:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
class Point
{
public:
    int x,y;
    Point(int _x=0,int _y=0):x(_x),y(_y){}
    friend long long cross(const Point &a,const Point &b)
    {
        return (long long)a.x*b.y-(long long)a.y*b.x;
    }
    friend Point operator - (const Point &a,const Point &b)
    {
        return Point(a.x-b.x,a.y-b.y);
    }
    int quadrant()const
    {
        if(x>0&&y>=0) return 1;
        else if(x<=0&&y>0) return 2;
        else if(x<0&&y<=0) return 3;
        else if(x>=0&&y<0) return 4;
        else return 0;
    }
	double angle()const
	{
		return atan2(y,x);
	}
};
bool cmp_polar_angle(const Point &a,const Point &b)
{
    int x=a.quadrant(),y=b.quadrant();
    if(x!=y) return x<y;
    else return cross(a,b)>0;
}
vector<int> convex_hull(const vector<Point> &p)
{
    int n=p.size();
    if(n<=2)
    {
        vector<int>res(n,0);
        for(int i=0;i<n;i++)
            res[i]=i;
        return res;
    }
    vector<int>id(n);
    iota(id.begin(),id.end(),0);
    sort(id.begin(),id.end(),[=](const int &a,const int &b){return p[a].x==p[b].x?p[a].y<p[b].y:p[a].x<p[b].x;});
    vector<int>stk;
    int top=0;
    for(int i=0;i<n;i++)
    {
        while(top>=2&&cross(p[stk[top-1]]-p[stk[top-2]],p[id[i]]-p[stk[top-1]])<=0) stk.pop_back(),top--;
        stk.emplace_back(id[i]),top++;
    }
    int tmp=top;
    for(int i=n-2;i>=0;i--)
    {
        while(top>tmp&&cross(p[stk[top-1]]-p[stk[top-2]],p[id[i]]-p[stk[top-1]])<=0) stk.pop_back(),top--;
        stk.emplace_back(id[i]),top++;
    }
    stk.pop_back(),top--;
    vector<int> hull;
    for(int i=0;i<top;i++)
        hull.emplace_back(stk[i]);
    return hull;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n;
    cin>>n;
    vector<Point>p(n);
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        p[i]=Point(x,y);
    }
    vector<int>q=convex_hull(p);
    vector<int>vis(n,0);
    for(int u:q)
        vis[u]=true;
    vector<int>pp(n);
	iota(pp.begin(),pp.end(),0);
    vector<double>dp(n);
    int ans=1;
    for(int x=0;x<n;x++)
        if(!vis[x])
        {
            for(int i=0;i<n;i++)
            {
				if(i==x) dp[i]=-1e9;
                else dp[i]=(p[i]-p[x]).angle();
            }
            sort(pp.begin(),pp.end(),[=](const int &a,const int &b){return dp[a]<dp[b];});
            for(int i=1;i<n;i++)
            {
                int j=i+1;
                if(j>=n) j=1;
                if(vis[pp[i]]&&vis[pp[j]]) ans++;
            }
        }
    cout<<ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 4044kb

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: