2 条题解
-
0
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; const double Pi=acos(-1.0); const double eps=1e-10; struct point { int x,y;double k; bool operator <(const point &b) const{return k<b.k;} }p[N<<1]; int main() { int n; scanf("%d",&n);if(n<=2){puts("0");return 0;} for(int i=1;i<=n;++i) { scanf("%d%d",&p[i].x,&p[i].y); p[i].k=atan2(p[i].y,p[i].x); } sort(p+1,p+1+n); ll ans=1ll*n*(n-1)*(n-2)/6; for(int i=n+1;i<=(n<<1);++i)p[i]=p[i-n],p[i].k+=2*Pi; for( int i=1,l,r=1;i<=n;++i) { l=i+1; while(p[r+1].k+eps<p[i].k+Pi)++r; ans-=1ll*(r-l+1)*(r-l)/2; } printf("%lld\n",ans); return 0; } -
0
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; const double Pi=acos(-1.0); const double eps=1e-10; struct point { int x,y;double k; bool operator <(const point &b) const{return k<b.k;} }p[N<<1]; int main() { int n; scanf("%d",&n);if(n<=2){puts("0");return 0;} for(int i=1;i<=n;++i) { scanf("%d%d",&p[i].x,&p[i].y); p[i].k=atan2(p[i].y,p[i].x); } sort(p+1,p+1+n); ll ans=1ll*n*(n-1)*(n-2)/6; for(int i=n+1;i<=n<<1;++i)p[i]=p[i-n],p[i].k+=2*Pi; for( int i=1,l,r=1;i<=n;++i) { l=i+1; while(p[r+1].k+eps<p[i].k+Pi)++r; ans-=1ll*(r-l+1)*(r-l)/2; } printf("%lld\n",ans); return 0; }
- 1
信息
- ID
- 1620
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 10
- 已通过
- 7
- 上传者