//!!in the name of god!!
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e18
#define F first
#define S second
#define PB push_back
#define PF push_front
#define pll pair<ll,ll>
#define pii pair<int,int>
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define MT(a,b,c) make_tuple(a,b,c)
#define has(a,b) (a.find(b)!=a.end())
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const int mx = 3e3+5;
typedef long double ld;
pll arr[mx];
int dir[mx];
pii sav[5]{
MP(0,0),
MP(-1,0),
MP(0,-1),
MP(1,0),
MP(0,1),
};
ld dp[mx];
inline int fix(int i,ll x,ll y){
int o=0;
if(abs(x-arr[i].F)>abs(y-arr[i].S)){
o=(x>arr[i].F)?3:1;
}
if(abs(x-arr[i].F)<abs(y-arr[i].S)){
o=(y>arr[i].S)?4:2;
}
return o;
}
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector<int> sp;
for(ll x,y,i=1;i<=n;i++){
cin>>x>>y;
arr[i]=MP(x,y);
if(1<i){
dir[i]=fix(i,arr[1].F,arr[1].S);
if(dir[i]==0){
sp.PB(i);
}
}
}
int o=1;
set<pair<ld,int>> lst;
for(int d=1;d<=4;d++){
dir[1]=d;
ll x=arr[1].F+sav[d].F;
ll y=arr[1].S+sav[d].S;
for(int i:sp){
dir[i]=fix(i,x,y);
}
fill(dp,dp+mx,inf);
lst.insert(MP(0,1));
while(!lst.empty()){
int i=lst.begin()->S;
ld di=lst.begin()->F;
dp[i]=min(dp[i],di);
lst.erase(lst.begin());
for(int j=1;j<=n;j++){
if(i!=j){
if(dir[i]%2==dir[j]%2){
ld v0,v1,d0,d1;
if(dir[i]%2){
v0=arr[i].F;
v1=arr[j].F;
d0=arr[i].S;
d1=arr[j].S;
}
else{
v0=arr[i].S;
v1=arr[j].S;
d0=arr[i].F;
d1=arr[j].F;
}
if(d0==d1){
if((v0<v1&&dir[i]>dir[j])||(v0>v1&&dir[i]<dir[j])){
ld t=((v0+v1)/(ld)2)-min(v0,v1);
if(di<t){
lst.insert(MP(t,j));
}
}
}
}
else{
int t=fix(i,arr[j].F,arr[j].S);
if(t==0){
bool xk=arr[j].F<arr[i].F?(dir[i]==1||dir[j]==3):(dir[i]==3||dir[j]==1);
bool yk=arr[j].S<arr[i].S?(dir[i]==2||dir[j]==4):(dir[i]==4||dir[j]==2);
if(xk&&yk){
if(di<abs(arr[i].F-arr[j].F)){
lst.insert(MP(abs(arr[i].F-arr[j].F),j));
}
}
}
}
}
}
}
int c=0;
for(int i=1;i<=n;i++){
c+=dp[i]<inf;
}
o=max(o,c);
}
cout<<o;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |