QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314271#7906. Almost ConvextaiyangfengTL 1ms4192kbC++202.4kb2024-01-25 15:09:512024-01-25 15:09:51

Judging History

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

  • [2024-01-25 15:09:51]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4192kb
  • [2024-01-25 15:09:51]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
#define int long long
constexpr double eps=1e-8;
constexpr double PI=acos(-1.0);
int sgn(double x){
  if(fabs(x)<eps)return 0;
  if(x>0)return 1;return -1;
}
struct Point{
  double x,y;
  Point(){}
  Point(double _x,double _y):x(_x),y(_y){}
  Point operator-(const Point&b)const{return(Point){x-b.x,y-b.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;}
  double operator*(const Point&b)const{return x*b.x+y*b.y;}
  bool operator<(const Point&b)const{return x<b.x||(x==b.x&&y<b.y);}
  bool operator==(const Point&b)const{return sgn(x-b.x)==0&&sgn(y-b.y)==0;}
  Point rotate(double B,Point P){return(Point){(x-P.x)*cos(B)-(y-P.y)*sin(B)+P.x,(x-P.x)*sin(B)+(y-P.y)*cos(B)+P.y};}
};
double dist(Point a,Point b){return sqrt((a-b)*(a-b));}
double len(Point a){return sqrt(a.x*a.x+a.y*a.y);}
Point p[2010],ch[2010];int vis[2010];
void ConvexHull(Point *p,int n,Point *ch){
  sort(p,p+n),n=unique(p,p+n)-p;
  int m=0,k;
  stack<int>ans;
  for(int i=0;i<n;++i){
    while(m>1&&sgn((ch[m-1]-ch[m-2])^(p[i]-ch[m-1]))<=0)--m,ans.pop();
    ch[m++]=p[i],ans.push(i);
  }k=m;
  for(int i=n-2;i>=0;--i){
    while(m>k&&sgn((ch[m-1]-ch[m-2])^(p[i]-ch[m-1]))<=0)--m,ans.pop();
    ch[m++]=p[i],ans.push(i);
  }if(n>1)--m,ans.pop();
  while(!ans.empty())vis[ans.top()]=1,ans.pop();
}
unordered_map<int,int>mp;
inline int getpoint(double x,double y){return (x+1000001)*2000001+y;}
inline int getpoint(Point i){return getpoint(i.x,i.y);}
Point C,P[2010];
bool cmp(Point a,Point b){
  a=a-C,b=b-C;
  if(atan2(a.y,a.x)!=atan2(b.y,b.x))
    return atan2(a.y,a.x)<atan2(b.y,b.x);
  else return a.x<b.x;
}
signed main(){
  int n,ans=0;cin>>n;
  for(int i=0;i<n;++i)cin>>p[i].x>>p[i].y;
  ConvexHull(p,n,ch);
  for(int i=0;i<n;++i)if(vis[i])mp[getpoint(p[i])]=1;
  for(int i=0;i<n;++i)if(!mp.count(getpoint(p[i]))){
    int cnt=0;for(int j=0;j<n;++j)if(j!=i)P[cnt++]=p[j];
    C=p[i];sort(P,P+cnt,cmp);
    //for(int j=0;j<cnt;++j)cout<<P[j].x<<' '<<P[j].y<<endl;
    //cout<<endl;
    for(int j=0;j<cnt;++j)if(mp.count(getpoint(P[j]))&&mp.count(getpoint(P[(j+1)%cnt])))
      ++ans;//cout<<p[i].x<<' '<<p[i].y<<' '<<P[j].x<<' '<<P[j].y<<' '<<P[(j+1)%cnt].x<<' '<<P[(j+1)%cnt].y<<endl;
  }
  cout<<ans+1<<endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: