PROBLEM LINK:
DIFFICULTY:
Medium
PREREQUISITES:
Geometry, Sweep Line
PROBLEM:
There are N isosceles right triangles with their hypotenuses on the x-axis. Find the number of regions that the sides of the triangles and the x-axis split the region y\ge 0 into.
QUICK EXPLANATION
This problem is the same as counting the number of intersections between perpendicular line segments, which can be solved with a sweep line algorithm.
EXPLANATION:
Observation 1. The answer is the (number of intersections not on the x-axis) + 1.
Proof
We can see that each region except for the outer region corresponds to an intersection point at the top of the region.
We can prove this more formally with Euler’s formula. Let there be x intersection points on the x-axis and y intersection points not on the x-axis. v=y+x because the nodes of the graph are the intersection points. e=2y+x-1 because each of the y intersection points not on the x-axis has two edges, one directing downward left and the other directing downward right, and there is an edge between each adjacent pair of the x intersection points on the x-axis. Finally, f=2-v+e=2-(y+x)+(2y+x-1)=y+1.
After this observation, this problem becomes a standard sweep line problem for counting the number of intersections between perpendicular line segments (although there are properties of this problem which makes it slightly easier than the general problem).
Let’s split each isosceles triangle into left and right segments. In the picture below, the left segment is in blue and the right segment is in green:
Note that the segments from different isosceles triangles may overlap, so we should get rid of the smaller segments in overlapping segments.
We will sweep over the left segments from left to right and count the answer for each left segment. While we sweep over the left segments, we should maintain a set of active right segments. Whenever we count the answer for a left segment, the set of active right segments should be the set of right segments that would intersect the left segment if it were extended to infinity (but note that the answer for the left segment is not simply the size of the set of active right segments).
Example
We start with the leftmost left segment, and there is one active right segment. We can check to see that there is one intersection.
We move on to the next left segment, and there are two active right segments. We can check to see that both of them intersect with the left segment.
We move on to the next left segment, and there are three active right segments because if we extended the left segment to infinity as shown in the picture, it would intersect all three active right segments. However, the left segment itself only intersects one of the right segments.
We move on to the last left segment, and there are two active right segments. Both of these right segments intersect with the left segment.
This idea of sweeping a line from left to right while maintaining some information (in our case, the set of active right segments) to compute information efficiently is the essence of a sweep line algorithm. I will now describe the details of this algorithm.
We can represent each left segment as a pair (l, r), meaning that it starts at point l on the x-axis and it extends far enough to be able to pair with a right segment starting at point r on the x-axis. Similarly, each right segment will also be represented as a pair (l, r), meaning that it starts at point r on the x-axis and will extend far enough to be able to pair with a left segment starting at point l on the x-axis.
Note that a right segment j will be active for all left segments i such that l_j \le l_i < r_j. We can make two events for this: when our sweep line first reaches l_j, we will add j to the active set, and when our sweep line first reaches r_j, we will remove j from the active set.
Now that we know how to maintain the set of active right segments while sweeping through left segments, how do we fine the number of right segments which intersect with the left segment? The only condition an active right segment j has to satisfy to intersect with left segment i is r_j \le r_i. In order to count this efficiently, we will use a data structure (such as Ordered Set PBDS in C++) which supports adding/removing elements and querying the number of elements less than or equal to a given element, all in O(\log N) time.
Some “guideline” on how I implemented the sweep line (for those who may be unfamiliar with it): There are three types of events, which are adding a right segment (at time l_j), removing a right segment (at time r_j), and querying a left segment (at time l_i). I created a struct called event, which stores the time the event happens, the type of the event, and some other information for the event. After I find all of the events, I sort them by time (and then by type) and I process them one by one.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define X first
#define Y second
typedef pair<int,int> pii;
const int MAXN = 1e5 + 10;
ordered_set s;
int n, t;
long long ans;
pii P[MAXN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--) {
ans = 0;
s.clear();
cin >> n;
for(int i = 0; i < n; i++)
cin >> P[i].X >> P[i].Y;
sort(P, P + n);
for(int i = 0; i < n; i++) {
while(s.size()) {
int tmp = *s.begin();
if(tmp <= P[i].X)
s.erase(s.begin());
else
break;
}
s.insert(P[i].Y);
if (i == n - 1 || P[i].X != P[i + 1].X)
ans += s.order_of_key(P[i].Y) + 1;
}
cout << ans + 1 <<endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int x[123456],y[123456];
pii forw[212345],backw[212345];
vector<vi> remov(212345);
int bit[212345];
int tot=0;
int update(int pos,int val){
while(pos<=212345){
bit[pos]+=val;
pos+=pos&(-pos);
}
tot+=val;
return 0;
}
int query(int pos){
int ans=0;
while(pos>0){
ans+=bit[pos];
pos-=pos&(-pos);
}
return ans;
}
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
map<int,int> mapi;
map<int,int>::iterator it;
int counter=1;
rep(i,n){
cin>>x[i]>>y[i];
mapi[x[i]]=1;
mapi[y[i]]=1;
}
for(it=mapi.begin();it!=mapi.end();it++){
it->ss=counter++;
}
rep(i,n){
x[i]=mapi[x[i]];
y[i]=mapi[y[i]];
}
rep(i,2*n+10){
remov[i].clear();
forw[i]=mp(-1,0);
backw[i]=mp(inf,0);
}
rep(i,n){
if(x[i]==y[i])
continue;
forw[x[i]]=max(forw[x[i]],mp(y[i],i));
backw[y[i]]=min(backw[y[i]],mp(x[i],i));
}
int j;
int ind;
ll ans=1;
tot=0;
rep(i,2*n+10){
if(backw[i].ff!=inf){
ind=backw[i].ss;
ans+=tot-query(x[ind]-1);
rep(j,remov[i].size()){
update(remov[i][j],-1);
}
}
if(forw[i].ff!=-1){
update(i,1);
remov[forw[i].ff].pb(i);
}
}
cout<<ans<<endl;
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define ar array
const int mxN=1e5;
int n, xl[mxN], xr[mxN];
struct event {
int x, type, y;
bool operator<(const event &o) {
return make_pair(x, type)<make_pair(o.x, o.type);
}
};
void solve() {
//input
cin >> n;
for(int i=0; i<n; ++i)
cin >> xl[i] >> xr[i];
//find the longest segments from overlaps
map<int, int> mpl, mpr;
for(int i=0; i<n; ++i) {
if(mpl.find(xl[i])==mpl.end())
mpl[xl[i]]=xr[i];
else
mpl[xl[i]]=max(xr[i], mpl[xl[i]]);
if(mpr.find(xr[i])==mpr.end())
mpr[xr[i]]=xl[i];
else
mpr[xr[i]]=min(xl[i], mpr[xr[i]]);
}
//create the events
vector<event> ve;
for(auto a : mpr) {
//xl[i] = a.second, xr[i] = a.first
//right segment i should be active in [xl[i], xr[i])
//add this right segment at time xl[i]
ve.push_back({a.second, 1, a.first});
//remove this right segment at time xr[i]
ve.push_back({a.first, 2, a.first});
}
for(auto a : mpl) {
//xl[i] = a.first, xr[i] = a.second
//query this segment which extends to xr[i] at time xl[i]
ve.push_back({a.first, 3, a.second});
}
sort(ve.begin(), ve.end());
//sweep
ll ans=0;
//data structure to store the active right segments
oset<int> s;
for(event e : ve) {
if(e.type==1) {
//add segment
s.insert(e.y);
} else if(e.type==2) {
//remove segment
s.erase(e.y);
} else {
//left segment i intersects right segment j if xr[j] <= xr[i]
//count right segments <= e.y
ans+=s.order_of_key(e.y+1);
}
}
cout << ans+1 << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 