#1907338

Solution for 2181: Neko's Treasure by dohatsu

Source Code Status Test Cases
    Policy: public     Reviewed: 66    
00.03 sec    1584 KB    87 lines     1718 bytes    2016-07-08 23:20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_R 10005

typedef complex<ll> P;

int n;
vector< P > G[MAX_R];
ll sx,sy,tx,ty;
P sp,tp;

int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    for(int i=0;i<MAX_R;i++)G[i].clear();
    cin>>sx>>sy>>tx>>ty;
    sp=P(sx,sy);
    tp=P(tx,ty);
    for(int i=0;i<n;i++){
      ll x,y,r;
      cin>>x>>y>>r;
      P p=P(x,y);
      if(norm(tp-p)==r*r||norm(sp-p)==r*r){
        assert(0);
      }
      
      if(norm(tp-p)<r*r&&norm(sp-p)<r*r)continue;
      if(norm(tp-p)>r*r&&norm(sp-p)>r*r)continue;
      G[r].push_back(p);
    }
    
    vector<P> A,B;
    vector<ll> Ar,Br;
    for(ll i=0;i<MAX_R;i++){
      for(int j=0;j<(int)G[i].size();j++){
        P p=G[i][j];
        if(norm(tp-p)<i*i){
          A.push_back(p);
          Ar.push_back(i);
        }
        if(norm(sp-p)<i*i){
          B.push_back(p);
          Br.push_back(i);
        }
      }
    }

    int ans=0;
    
    vector<int> dpA(A.size(),1);
    vector<int> dpB(B.size(),1);

    for(int i=0;i<(int)A.size();i++){
      for(int j=0;j<i;j++){
        if( norm(A[i]-A[j])  < (Ar[i]-Ar[j])*(Ar[i]-Ar[j]) ){
          dpA[i]=max(dpA[i],dpA[j]+1);
        }
      }
      ans=max(ans,dpA[i]);
    }

    for(int i=0;i<(int)B.size();i++){
      for(int j=0;j<i;j++){
        if( norm(B[i]-B[j]) < (Br[i]-Br[j])*(Br[i]-Br[j]) ){
          dpB[i]=max(dpB[i],dpB[j]+1);
        }
      }
      ans=max(ans,dpB[i]);
    }

    for(int i=0;i<(int)A.size();i++){
      for(int j=0;j<(int)B.size();j++){
        if( norm(A[i]-B[j]) > (Ar[i]+Br[j])*(Ar[i]+Br[j]) ){
          ans=max(ans,dpA[i]+dpB[j]);
        }
      }
    }

    cout<<ans<<endl;
    
  }
  return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 C++ CPU: 00.03 sec Memory: 1584 KB Length: 1718 B 2016-07-08 23:20 2016-07-08 23:20
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.03 sec 1584 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags