Proficient.
Put your skills to the test.

Problem summary

N particles start at positive positions on the x-axis and move upward; N others start on the y-axis and move right. Each has a fixed positive speed. Opposite kinds annihilate on collision, releasing one energy unit. Find the total energy.

Constraints

1 ≤ N ≤ 400000; coordinates and speeds ≤ 10^9. Particles starting at the same point have distinct speeds.

Worked example

An independently prepared example for this explanation.

3
1 3
3 4
4 2
2 6
3 1
5 2

2

Solution analysis

1. A vertical particle (x,v) and horizontal particle (y,w) meet when y/v=x/w, or equivalently xv=yw. Thus particles split into independent groups by the product of their starting coordinate and speed.
2. Within one product group every vertical particle could collide with every horizontal particle if both survive until their meeting time. The earliest remaining meeting annihilates one of each kind. As long as both kinds remain, another meeting must still lie in the future: otherwise those two surviving particles would already have collided. Consequently exactly the smaller group count is annihilated.
3. The sample products are 3,12,8 for vertical particles and 12,3,10 for horizontal ones. Products 3 and 12 each contribute one collision; the unmatched products contribute none. Sort both product lists and match equal values with two pointers.

Why it works

Collisions are impossible across unequal-product groups. In an equal-product group, a surviving pair cannot have passed its intersection time. Hence the process cannot end while both kinds survive. Each collision removes one of each kind, so its total is the minimum of the two counts. Matching the sorted lists sums these minima.

Watch out. Use 64-bit multiplication: products can reach 10^18. Do not compare floating-point collision times or assume the initial coordinates must be distinct.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    cin>>count;
    vector<long long>vertical(count),horizontal(count);
    for(auto&product:vertical){
        long long coordinate,speed;
        cin>>coordinate>>speed;
        product=coordinate*speed;
    }
    for(auto&product:horizontal){
        long long coordinate,speed;
        cin>>coordinate>>speed;
        product=coordinate*speed;
    }
    sort(vertical.begin(),vertical.end());
    sort(horizontal.begin(),horizontal.end());
    int i=0;
    int j=0;
    int energy=0;
    while(i<count&&j<count){
        if(vertical[i]<horizontal[j]){
            i++;
        }
        else if(horizontal[j]<vertical[i]){
            j++;
        }
        else{
            // One particle of each kind is consumed for this common product.
            energy++;
            i++;
            j++;
        }
    }
    cout<<energy<<'\n';
}