This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int Inf = 1'000'000'010;
int n;
int x[N], y[N];
int dir[N];
pii vec[] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
set< pair<int, int> > st; // time, id
int mk[N];
int Collision(int a, int b){
if(x[a] > x[b]) swap(a, b);
int dp_a = x[a] + y[a];
int dp_b = x[b] + y[b];
int dn_a = x[a] - y[a];
int dn_b = x[b] - y[b];
if(dp_a != dp_b && dn_a != dn_b)
return Inf;
int d = abs(x[a] - x[b]);
if(dp_a == dp_b){
if((dir[a] == 0 && dir[b] == 3) || (dir[a] == 1 && dir[b] == 2))
return d;
return Inf;
}
if((dir[a] == 0 && dir[b] == 1) || (dir[a] == 3 && dir[b] == 2))
return d;
return Inf;
}
void Infect(int u, int tm){
mk[u] = 1;
for(int i = 0; i < n; i++){
if(mk[i]) continue;
int ds = Collision(u, i);
if(ds >= tm && ds != Inf){
st.insert({ds, i});
}
}
}
int Solve(){
dir[0] = 0;
for(int i = 1; i < n; i++){
int X = abs(x[i] - x[0]);
int Y = abs(y[i] - y[0]);
if(X == Y){
if(x[i] < x[0]) dir[i] = 0;
else dir[i] = y[i] < y[0] ? 3 : 1;
} else {
if(X > Y){
if( x[i] < x[0]) dir[i] = 0;
else dir[i] = 2;
} else {
if( y[i] < y[0]) dir[i] = 3;
else dir[i] = 1;
}
}
}
// cerr << "!! " ;
// for(int i = 0; i < n; i++){
// cerr << dir[i] << ' ';
// }
// cerr << '\n';
memset(mk, 0, sizeof mk);
st.insert({0, 0});
while(!st.empty()){
int fr = st.begin() -> S;
int tm = st.begin() -> F;
st.erase(st.begin());
Infect(fr, tm);
}
int res = 0;
for(int i = 0; i < n; i++)
res += mk[i];
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> x[i] >> y[i];
int ans = 0;
for(int _ = 0; _ < 4; _++){
ans = max(ans, Solve());
for(int i = 0; i < n; i++){
int _x = x[i];
x[i] = -y[i];
y[i] = _x;
}
// break;
}
cout << ans << '\n';
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... |