結果
問題 | No.947 ABC包囲網 |
ユーザー |
|
提出日時 | 2019-12-17 16:18:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 792 bytes |
コンパイル時間 | 1,337 ms |
コンパイル使用メモリ | 95,428 KB |
最終ジャッジ日時 | 2025-01-08 11:54:57 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <math.h> using namespace std; typedef long long int ll; int n; ll x[4040],y[4040]; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); long double pi=4*atan(1); cin >> n; vector<long double> v; for(int i=0;i<n;i++){ cin >> x[i] >> y[i]; ll g=__gcd(abs(x[i]),abs(y[i])); if(g==0){ i--; n--; break; } v.push_back(atan2(y[i],x[i])); v.push_back(atan2(y[i],x[i])+2*pi); v.push_back(atan2(y[i],x[i])+4*pi); } sort(v.begin(),v.end()); ll ret=0; for(int i=0;i<n;i++){ int j=i; while(v[j]-v[i]<=pi+1e-12)j++; int y=j; for(int x=i+1;x<j;x++){ if(v[i]!=v[x]){ if(v[x]-v[i]>=pi-1e-12)break; while(v[y]-v[x]<pi-1e-12)y++; ret+=(y-j); } } } cout << ret/3 << endl; }