結果

問題 No.947 ABC包囲網
ユーザー ttttan2ttttan2
提出日時 2019-12-10 23:02:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,638 ms / 2,000 ms
コード長 4,750 bytes
コンパイル時間 2,308 ms
コンパイル使用メモリ 165,752 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-06 07:49:57
合計ジャッジ時間 38,782 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,384 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 3 ms
4,376 KB
testcase_18 AC 4 ms
4,376 KB
testcase_19 AC 4 ms
4,380 KB
testcase_20 AC 4 ms
4,380 KB
testcase_21 AC 4 ms
4,380 KB
testcase_22 AC 4 ms
4,376 KB
testcase_23 AC 4 ms
4,380 KB
testcase_24 AC 4 ms
4,380 KB
testcase_25 AC 4 ms
4,380 KB
testcase_26 AC 4 ms
4,380 KB
testcase_27 AC 4 ms
4,380 KB
testcase_28 AC 1,514 ms
4,380 KB
testcase_29 AC 1,426 ms
4,376 KB
testcase_30 AC 1,255 ms
4,380 KB
testcase_31 AC 1,431 ms
4,376 KB
testcase_32 AC 1,441 ms
4,380 KB
testcase_33 AC 1,427 ms
4,380 KB
testcase_34 AC 1,437 ms
4,384 KB
testcase_35 AC 1,426 ms
4,376 KB
testcase_36 AC 1,447 ms
4,380 KB
testcase_37 AC 1,441 ms
4,380 KB
testcase_38 AC 1,438 ms
4,380 KB
testcase_39 AC 1,446 ms
4,376 KB
testcase_40 AC 1,632 ms
4,380 KB
testcase_41 AC 1,628 ms
4,376 KB
testcase_42 AC 1,631 ms
4,376 KB
testcase_43 AC 1,617 ms
4,380 KB
testcase_44 AC 1,625 ms
4,384 KB
testcase_45 AC 1,638 ms
4,376 KB
testcase_46 AC 1,634 ms
4,380 KB
testcase_47 AC 1,625 ms
4,380 KB
testcase_48 AC 1,624 ms
4,376 KB
testcase_49 AC 1,433 ms
4,380 KB
testcase_50 AC 1,614 ms
4,376 KB
testcase_51 AC 2 ms
4,380 KB
testcase_52 AC 2 ms
4,380 KB
testcase_53 AC 2 ms
4,380 KB
testcase_54 AC 2 ms
4,380 KB
testcase_55 AC 2 ms
4,380 KB
testcase_56 AC 1 ms
4,380 KB
testcase_57 AC 5 ms
4,380 KB
testcase_58 AC 6 ms
4,380 KB
testcase_59 AC 6 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
bool cmp(pll a,pll b){
    if(a.first*b.first<0)return a.first>b.first;
    if(a.first==0){
        if(b.first==0){
            if(a.second==-1)return true;
            else return false;
        }
        if(a.second==1){
            if(b.first>0)return false;
            else return  true;
        }
        if(a.second==-1){
            return true;
        }
    }
    if(b.first==0){
        if(b.second==-1)return false;
        else{
            if(a.first>0)return true;
            else return false;
        }
    }
    return a.second*b.first<a.first*b.second;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    //cout<<acos(0.5)*180/pi;return 0;
    vector<pll> v[2];
    int r[2]={0,0};
    map<pll,ll> mp;
    rep(i,0,n){
        ll a,b;cin>>a>>b;
        ll c=gcd(abs(a),abs(b));
        if(a==0){
            if(b==0)continue;
            if(b>0)r[0]++;
            else r[1]++;
            continue;
        }
        if(mp[{a/c,b/c}]){mp[{a/c,b/c}]++;continue;}
        mp[{a/c,b/c}]=1;
        if(a>0)v[0].push_back({a/c,b/c});
        else v[1].push_back({a/c,b/c});
    }
    //cout<<r[0]<<" "<<r[1]<<endl;
    sort(v[0].begin(),v[0].end(),cmp);
    sort(v[1].begin(),v[1].end(),cmp);
    vector<pll> w;
    if(r[1])w.push_back({0,-1});
    rep(i,0,v[0].size())w.push_back(v[0][i]);
    if(r[0])w.push_back({0,1});
    rep(i,0,v[1].size())w.push_back(v[1][i]);
    mp[{0,1}]=r[0];
    mp[{0,-1}]=r[1];
    ll mae[w.size()];
    ll saki[w.size()];
    rep(i,0,w.size()){
        ll u=i,d=-1;
        ll f=-w[i].first,g=-w[i].second;
        pll pp={f,g};
        if(f<0){
            mae[i]=-1;
            continue;
        }
        while(u-d>1){
            ll mid=(u+d)/2;
            if(pp==w[mid]){
                d=mid;
                continue;
            }
            if(cmp(w[mid],pp))d=mid;
            else u=mid;
        }
        mae[i]=d;
    }
    rep(i,0,w.size()){
        ll u=w.size(),d=i;
        ll f=-w[i].first,g=-w[i].second;
        pll pp={f,g};
        if(f>0){
            saki[i]=w.size()-1;
            continue;
        }
        if(f==0&&g==-1){
            saki[i]=w.size()-1;
            continue;
        }
        while(u-d>1){
            ll mid=(u+d)/2;
            if(pp==w[mid]){
                d=mid;
                continue;
            }
            if(cmp(w[mid],pp))d=mid;
            else u=mid;
        }
        saki[i]=d;
    }
    rep(i,0,w.size()){
      //cout<<saki[i]<<endl;
    }//return 0;
    rep(i,0,w.size()){
       // cout<<w[i].first<<" "<<w[i].second<<" "<<mp[w[i]]<<endl;
    }
    ll ans=0;
    rep(i,0,w.size()){
        ll dp[w.size()+1][3];
        memset(dp,0,sizeof dp);
        dp[i][0]=mp[w[i]];
        //ll now=i;
        ll sum[w.size()+1][3];
        memset(sum,0,sizeof sum);
        sum[i+1][0]=dp[i][0];
        rep(j,i+1,w.size()){
            rep(k,1,3){
                dp[j][k]=mp[w[j]]*(sum[j][k-1]-sum[mae[j]+1][k-1]);
                sum[j+1][k]=sum[j][k]+dp[j][k];
            }
            sum[j+1][0]=sum[j][0];
        }
        
        ll ee=saki[i];
        ee++;
        if(ee<w.size()){
            pll pp={-w[i].first,-w[i].second};
            if(pp==w[ee])ee++;
        }
        rep(j,ee,w.size()){
            ans+=dp[j][2];
        }
        //cout<<ee<<endl;
        /*if(i==1){
            rep(j,0,w.size()){
                rep(k,0,3)cout<<dp[j][k]<<" ";
                cout<<endl;
            }
        }*/
    }
    cout<<ans<<endl;
}
0