PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Alei Reyes
Tester: Suchan Park
Editorialist: William Lin
DIFFICULTY:
PROBLEM:
There are N points. In one operation, you can choose a convex polygon P from those points. Let M be the number of points of P. The sum of M over all operations should be \le 5\cdot 10^5. For each i from 1 to M-1, consider the segment from P_i to P_{i+1}. Move P_i to the nearest lattice point on the segment. Whenever two points coincide, they merge together and always move as one point afterwards. Find the minimum number of operations to merge all points.
Observations:
- The coordinates are relatively small (at most 1024) compared to N (around 2^{17}).
- This means each row / column should have an average of at least 100 points.
Simplest Valid Solution:
Since each row should have at least one point, for some point (x1, y1), there should exist some point (x2, y2) with x2=x1+1. Since the points are in adjacent rows, there can’t be any lattice points on the segment connecting them, so the two points can be merged in just one operation.
The full algorithm is to start from the bottom row and merge each point in one row with a point in the next row. After that, all points with be on the last row and we can finish by merging them from left to right (the coordinates are small so this doesn’t waste too many operations).
Code
#include <bits/stdc++.h>
using namespace std;
#define ar array
int n;
vector<ar<int, 2>> v[1030];
vector<vector<int>> ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//input
cin >> n;
for(int i=0, x, y; i<n; ++i) {
cin >> x >> y;
v[x].push_back({y, i});
}
int x=0;
while(1) {
if(v[x+1].empty())
break;
//merge all points on row i with a point on row i+1
for(ar<int, 2> a : v[x])
ans.push_back({a[1], v[x+1][0][1]});
++x;
}
//all points on the last row, merge them
sort(v[x].begin(), v[x].end());
for(int i=0; i+1<v[x].size(); ++i) {
//the first i points have been merged
//now merge point i+1
while(v[x][i][0]<v[x][i+1][0]) {
ans.push_back({v[x][i][1], v[x][i+1][1]});
//in one operation, point i becomes 1 closer
++v[x][i][0];
}
}
//output
cout << ans.size() << "\n";
for(vector<int> a : ans) {
cout << a.size();
for(int ai : a)
cout << " " << ai+1;
cout << "\n";
}
}
Bigger polygons:
The previous solution is inefficient because we only merge two points for each operation. If we can somehow choose bigger polygons, we can merge more points for each operation, which will decrease the number of operations.
We can basically use the same solution as before, but we will try to add as many points in the next few rows to our polygon while making sure it is still convex.
Code
#include <bits/stdc++.h>
using namespace std;
#define ar array
int n;
vector<ar<int, 2>> v[1030];
vector<vector<ar<int, 2>>> ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//input
cin >> n;
for(int i=0, x, y; i<n; ++i) {
cin >> x >> y;
v[x].push_back({y, i});
}
int x=0;
while(1) {
if(v[x+1].empty())
break;
//merge all points on row i with a point on row i+1
for(ar<int, 2> a : v[x]) {
vector<ar<int, 2>> c={a, v[x+1][0]};
int x2=x+1;
while(v[x2].size()>1&&!v[x2+1].empty()) {
//find some point on row x2+1
bool ok=0;
for(ar<int, 2> b : v[x2+1]) {
//check cross product to check convexity
if(c.back()[0]-c[c.size()-2][0]>b[0]-c.back()[0]) {
c.push_back(b);
ok=1;
break;
}
}
if(ok) {
//point at row x2 is merged to x2+1
v[x2].erase(find(v[x2].begin(), v[x2].end(), c[c.size()-2]));
} else
break;
++x2;
}
ans.push_back(c);
}
++x;
}
//all points on the last row, merge them
sort(v[x].begin(), v[x].end());
for(int i=0; i+1<v[x].size(); ++i) {
//the first i points have been merged
//now merge point i+1
while(v[x][i][0]<v[x][i+1][0]) {
ans.push_back({v[x][i], v[x][i+1]});
//in one operation, point i becomes 1 closer
++v[x][i][0];
}
}
//output
cout << ans.size() << "\n";
for(vector<ar<int, 2>> a : ans) {
cout << a.size();
for(ar<int, 2> ai : a)
cout << " " << ai[1]+1;
cout << "\n";
}
}
Better polygon finder:
Finding next lattice point on a segment
Let the first point be (x1, y1) and the second point be (x2, y2). The vector from the first point to the second point is (vx, vy)=(x2-x1, y2-y1). If g=\gcd(vx, vy), the next lattice point on the segment will be (x1+\frac{vx}{g}, y1+\frac{vy}{g}).
It follows that if g=1 then there are no intermediate lattice points on the segment.
While there are still points left, we will take a random subset of at most 30 points (if we take too many then we will exceed the time limit). We will calculate the convex hull of the subset, but if we form a segment with an intermediate lattice point, then we will ignore the point. The goal of this is to make sure all points on the polygon of the convex hull can be merged into one point.
At some point when there are very few points left, it could be very hard to find any polygon. When that happens, merge two points at once until all remaining points have been merged.
Code
#include <bits/stdc++.h>
using namespace std;
#define ar array
int n;
vector<ar<int, 3>> v;
vector<vector<ar<int, 3>>> ans;
vector<bool> del;
//distance squared
int ds(ar<int, 3> a, ar<int, 3> b) {
return (a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]);
}
//cross product
int cp(ar<int, 3> o, ar<int, 3> a, ar<int, 3> b) {
return (a[0]-o[0])*(b[1]-o[1])-(a[1]-o[1])*(b[0]-o[0]);
}
//convex hull with graham's scan
vector<ar<int, 3>> ch(vector<ar<int, 3>> u) {
sort(u.begin(), u.end());
sort(u.begin()+1, u.end(), [&](const ar<int, 3> &i, const ar<int, 3> &j) {
int cpv=cp(u[0], i, j);
if(cpv>0)
return false;
if(cpv<0)
return true;
return ds(u[0], i)<ds(u[0], j);
});
vector<ar<int, 3>> ch;
for(int i=0; i<u.size(); ++i) {
while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[i])>=0)
ch.pop_back();
//make sure no intermediate lattice points
if(ch.empty()||abs(__gcd(u[i][0]-ch.back()[0], u[i][1]-ch.back()[1]))==1)
ch.push_back(u[i]);
}
if(ch.size()>2)
while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[0])>=0)
ch.pop_back();
return ch;
}
//find the next point on a segment
ar<int, 3> next_on_segment(ar<int, 3> a, ar<int, 3> b) {
ar<int, 2> v{b[0]-a[0], b[1]-a[1]};
int g=abs(__gcd(v[0], v[1]));
return {a[0]+v[0]/g, a[1]+v[1]/g, a[2]};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//input
cin >> n;
for(int i=0, x, y; i<n; ++i) {
cin >> x >> y;
v.push_back({x, y, i});
}
del=vector<bool>(n);
int lastsize=n, halt=0;
while(v.size()>1) {
random_shuffle(v.begin(), v.end());
for(int i=0; i<v.size(); i+=2000) {
//take subset
vector<ar<int, 3>> sub(v.begin()+i, v.begin()+i+min(2000, (int)v.size()-i));
//find convex hull
vector<ar<int, 3>> c=ch(sub);
if(c.size()<2)
continue;
//delete points except for last
for(int i=0; i+1<c.size(); ++i)
del[c[i][2]]=1;
ans.push_back(c);
}
//update v
vector<ar<int, 3>> v2;
for(ar<int, 3> a : v)
if(!del[a[2]])
v2.push_back(a);
v=v2;
if(lastsize>v.size()) {
lastsize=v.size();
halt=0;
} else
++halt;
if(halt>9)
break;
}
//merge two points at once
//sort to avoid accidentally merging with other points
sort(v.begin(), v.end());
for(int i=0; i+1<v.size(); ++i) {
//points 0 to i have been merged
//now merge point i+1
while(v[i][0]!=v[i+1][0]||v[i][1]!=v[i+1][1]) {
v[i]=next_on_segment(v[i], v[i+1]);
ans.push_back({v[i], v[i+1]});
}
}
//output
cout << ans.size() << "\n";
for(vector<ar<int, 3>> a : ans) {
cout << a.size();
for(ar<int, 3> ai : a)
cout << " " << ai[2]+1;
cout << "\n";
}
}
There’s a heuristic we can add. If the subset has points spread around the grid, then the convex hull will likely only contain the points near the outer part of the grid. We can group the points into subsets by their distance from the center of the grid.
Code
#include <bits/stdc++.h>
using namespace std;
#define ar array
int n;
vector<ar<int, 3>> v;
vector<vector<ar<int, 3>>> ans;
vector del;
//distance squared
int ds(ar<int, 3> a, ar<int, 3> b) {
return (a[0]-b[0])(a[0]-b[0])+(a[1]-b[1])(a[1]-b[1]);
}
//cross product
int cp(ar<int, 3> o, ar<int, 3> a, ar<int, 3> b) {
return (a[0]-o[0])(b[1]-o[1])-(a[1]-o[1])(b[0]-o[0]);
}
//convex hull with graham’s scan
vector<ar<int, 3>> ch(vector<ar<int, 3>> u) {
sort(u.begin(), u.end());
sort(u.begin()+1, u.end(), [&](const ar<int, 3> &i, const ar<int, 3> &j) {
int cpv=cp(u[0], i, j);
if(cpv>0)
return false;
if(cpv<0)
return true;
return ds(u[0], i)<ds(u[0], j);
});
vector<ar<int, 3>> ch;
for(int i=0; i<u.size(); ++i) {
while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[i])>=0)
ch.pop_back();
//make sure no intermediate lattice points
if(ch.empty()||abs(__gcd(u[i][0]-ch.back()[0], u[i][1]-ch.back()[1]))==1)
ch.push_back(u[i]);
}
if(ch.size()>2)
while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[0])>=0)
ch.pop_back();
return ch;
}
//find the next point on a segment
ar<int, 3> next_on_segment(ar<int, 3> a, ar<int, 3> b) {
ar<int, 2> v{b[0]-a[0], b[1]-a[1]};
int g=abs(__gcd(v[0], v[1]));
return {a[0]+v[0]/g, a[1]+v[1]/g, a[2]};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//input
cin >> n;
for(int i=0, x, y; i<n; ++i) {
cin >> x >> y;
v.push_back({x, y, i});
}
del=vector<bool>(n);
int lastsize=n, halt=0;
while(v.size()>1) {
if(halt<1) {
sort(v.begin(), v.end(), [](const ar<int, 3> &i, const ar<int, 3> &j) {
return (i[0]-512)*(i[0]-512)+(i[1]-512)*(i[1]-512)<(j[0]-512)*(j[0]-512)+(j[1]-512)*(j[1]-512);
});
} else
random_shuffle(v.begin(), v.end());
for(int i=0; i<v.size(); i+=2000) {
//take subset
vector<ar<int, 3>> sub(v.begin()+i, v.begin()+i+min(2000, (int)v.size()-i));
//find convex hull
vector<ar<int, 3>> c=ch(sub);
if(c.size()<2)
continue;
//delete points except for last
for(int i=0; i+1<c.size(); ++i)
del[c[i][2]]=1;
ans.push_back(c);
}
//update v
vector<ar<int, 3>> v2;
for(ar<int, 3> a : v)
if(!del[a[2]])
v2.push_back(a);
v=v2;
if(lastsize>v.size()) {
lastsize=v.size();
halt=0;
} else
++halt;
if(halt>9)
break;
}
//merge two points at once
//sort to avoid accidentally merging with other points
sort(v.begin(), v.end());
for(int i=0; i+1<v.size(); ++i) {
//points 0 to i have been merged
//now merge point i+1
int j=i+1;
//try to find next row
while(j<v.size()&&v[j][0]==v[i][0])
++j;
if(j>=v.size())
j=i+1;
while(v[i][0]!=v[j][0]||v[i][1]!=v[j][1]) {
v[i]=next_on_segment(v[i], v[j]);
ans.push_back({v[i], v[j]});
}
}
//output
cout << ans.size() << "\n";
for(vector<ar<int, 3>> a : ans) {
cout << a.size();
for(ar<int, 3> ai : a)
cout << " " << ai[2]+1;
cout << "\n";
}
}
Other solutions?
Note that in the solutions presented above, the segments from the polygons never contain lattice points which are not endpoints. This makes the code a lot easier as we don’t need to take care of the case when vertices on the polygon merge with points on the segments of the polygon. However, this also limits how efficient our solution can be, so if you take the time to write the code to account for polygons with segments with intermediate lattice points, the score should improve.