PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Sahil Tiwari
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
3056
PREREQUISITES:
None
PROBLEM:
There are N points lying on the coordinate axes.
In one second, you can draw some segments joining pairs of these points, as long as no two segments intersect non-trivially.
How many seconds do you need to draw every segment?
EXPLANATION:
Since all the points lie on the axes. every line segment we draw will be one of two types:
- Either it will lie completely on one of the coordinate axes; or
- It will lie entirely in one of the four quadrants.
Now, note that:
- Two line segments in different quadrants can never intersect nontrivially
- A line segment on an axis and another one in a quadrant can never intersect nontrivially
This gives us an idea to solve the problem: separately find the minimum time required to draw line segments in each quadrant, and along the axes. The final answer is the maximum of these times.
Let’s look at them separately.
Quadrants
Let’s consider the first quadrant, i.e, points (x, y) with x, y \gt 0.
Suppose there are k_1 points on the positive y-axis and k_2 points on the positive x-axis.
Then, it can be seen that you need \min(k_1, k_2) seconds to draw all pairs of segments between them.
Proof
Let y_1 \lt y_2 \ldots \lt y_{k_1} and x_1 \lt x_2 \lt \ldots \lt x_{k_2} be the coordinates.
Consider what happens when we draw the segment joining (0, y_{k_1}) and (x_1, 0).
It is now impossible for us to draw any segment from (0, y_s) to (x_t, 0) if s \lt k_1 and t \gt 0.
So, the best we can do is join y_{k_1} to all the x-points, and x_1 to all the y-points in this second.
Now we’ve drawn all segments from y_{k_1} and x_1, so we ignore them and continue on.
It’s easy to see that this process will take exactly \min(k_1, k_2) seconds to draw all pairs of segments since that’s when one side is exhausted, and it’s impossible to do any better.
So, just knowing the number of points on the axes for each quadrant will allow us to compute the answer for each one.
Axes
Segments on the axes are a bit trickier to handle.
There are two types of segments: ones lying on the x-axis, and ones lying on the y-axis.
Note that this time, there can be intersection between these different types of segments: but this intersection can only happen at the origin.
First, let’s look at segments that cross the origin.
Notice that any step can contain at most one segment crossing the origin along the x-axis and at most one segment crossing the origin along the y-axis; but it also can’t contain both of these.
In other words, each step can contain at most one segment crossing the origin. So, let’s compute the total number of these.
Suppose there are c_1 segments crossing the origin along the x-axis and c_2 along the y-axis. The answer is at least c_1 + c_2.
Computing c_1 and c_2 is easy: if there are p points with positive x-coordinate, and n with negative, then c_1 = p\cdot n.
c_2 can be computed similarly.
Now, let’s look at all segments on the axes.
Suppose there are m points on the x-axis. Then, we need a minimum of \left\lfloor \frac{m}{2}\right\rfloor \cdot \left\lceil \frac{m}{2}\right\rceil seconds to draw all pairs of segments between them.
Proof
For convenience, let m = 2k+1.
Let the points be x_1 \lt x_2 \lt \ldots \lt x_m.
Consider x_{k+1}.
- There are k points to its left and to its right.
- Any segment joining one point from the left and one point from the right needs its own second to be drawn, giving us k^2 seconds at least.
- Finally, we also need to draw segments from x_{k+1} itself. This can be done in k seconds by spreading outwards in both directions from x_{k+1}.
- Thus, we need k\cdot (k+1) seconds at minimum, which is exactly \left\lfloor \frac{m}{2}\right\rfloor \cdot \left\lceil \frac{m}{2}\right\rceil.
When m = 2k, a similar analysis will give you k\cdot(k-1) + k = k^2 seconds, which once again matches that formula.
So, compute this value for the x-axis and y-axis separately, and take the maximum of both.
Note that while the latter computation does include segments that cross the origin, it doesn’t matter: the value we computed is a clear lower bound for the answer, and it is also achievable.
Whenever we choose an origin-crossing x-segment, we can combine it with non-origin-crossing y-segments and vice-versa.
If non-crossing segments on one side run out, then we are limited by c_1 + c_2 from above anyway, so it causes no issues.
When we choose a y-segment that cross the origin, we can
The final answer is then the maximum value among everything computed above.
The only thing we did was count the number of points on the positive/negative x/y axes, which can be done in \mathcal{O}(N).
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#include<bits/stdc++.h>
#define int long long int
#define endl "\n"
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
signed main()
{
quick;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a = 0, b = 0, c = 0, d = 0, o = 0;
while(n--){
int x , y;
cin>>x>>y;
if(x==0 && y==0){
o++;
}
else if(y>0)
c++;
else if(y<0)
d++;
else if(x>0)
a++;
else
b++;
}
// cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
int k = a+b+o;
int A = k%2 ? k/2*(k/2+1) : k*k / 4;
k = c+d+o;
int B = k%2 ? k/2*(k/2+1) : k*k / 4;
int X = A - a*b;
int Y = B - c*d;
// cout<<A<<" "<<B<<endl;
int ans = A + B - min(a*b , Y) - min(c*d , X);
X -= min(c*d , X);
Y -= min(a*b , Y);
ans -= min(X , Y);
ans = max(ans , max({min(a , c) , min(a , d) , min(b , d) , min(b , c)}));
cout<<ans<<endl;
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e5);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(2, 1e6);
in.readEoln();
sn += n;
set<pair<int, int>> st;
int px = 0, nx = 0, py = 0, ny = 0;
for (int i = 0; i < n; i++) {
int x = in.readInt(-1e9, 1e9);
in.readSpace();
int y = in.readInt(-1e9, 1e9);
in.readEoln();
assert(x == 0 || y == 0);
st.emplace(x, y);
if (x > 0) {
px++;
}
if (x < 0) {
nx++;
}
if (y > 0) {
py++;
}
if (y < 0) {
ny++;
}
}
assert(n == (int) st.size());
long long ans = min(max(px, nx), max(py, ny));
ans = max(ans, px * 1LL * nx + py * 1LL * ny);
int cx = px + nx, cy = py + ny;
if (cx + cy == n - 1) {
cx++;
cy++;
}
ans = max(ans, (cx - cx / 2) * 1LL * (cx / 2));
ans = max(ans, (cy - cy / 2) * 1LL * (cy / 2));
cout << ans << '\n';
}
assert(sn <= 1e6);
in.readEof();
return 0;
}
Tester's code (C++)
//Utkarsh.25dec
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sumN=0;
void solve()
{
int n=readInt(2,1000000,'\n');
sumN+=n;
assert(sumN<=1000000);
set <pair<int,int>> s;
ll cntx=0,cnty=0,posx=0,negx=0,posy=0,negy=0;
for(int i=1;i<=n;i++)
{
ll x,y;
x=readInt(-1000000000,1000000000,' ');
y=readInt(-1000000000,1000000000,'\n');
s.insert(mp(x,y));
assert(x==0 || y==0);
if(x==0)
cnty++;
if(y==0)
cntx++;
if(x<0)
negx++;
if(x>0)
posx++;
if(y<0)
negy++;
if(y>0)
posy++;
}
assert(s.size()==n);
ll ans=0;
ans=max(ans,min(max(negx,posx),max(negy,posy)));
ans=max(ans,posx*negx+posy*negy);
ll A=((cntx+1)/2)*(cntx/2);
ll B=((cnty+1)/2)*(cnty/2);
ans=max(ans,max(A,B));
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,100000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}