November Rain

#include <iostream>
#include <stack>
#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
 
struct P{
	int first, second, third, fourth;
	P(){};
	P(int _f, int _s, int _t, int _ff):first(_f), second(_s), third(_t), fourth(_ff){}
	bool operator<(const P& p) const
	{
		if(first != p.first)
			return first < p.first;
		if(fourth == 1 && p.fourth == 0)
			return true;
		else if(fourth == 0 && p.fourth == 1)
			return false;
		if(fourth == 0 && p.fourth == 0)
			return third > p.third;
		else
			return third < p.third;
	}
};
 
#define vp vector<P>
#define vi vector<int>
 
int n;
int X1[40000], X2[40000], Y1[40000], Y2[40000];
 
vp v;
 
vi graph[40000];
int pure[40000];
 
int order[40000];
bool done[40000];
 
void topologicalSort()
{
	int idx = 0;
	stack<int> st;
	memset(done, 0, sizeof done);
	for(int i = 0; i < n; i ++)
		if(!done[i])
		{
			st.push(i);
			while(!st.empty())
			{
				int t = st.top();
				bool can_be_done = true;
				for(int j = 0; j < graph[t].size(); j ++)
					if(!done[graph[t][j]])
					{
						st.push(graph[t][j]);
						can_be_done = false;
					}
				if(can_be_done)
				{
					order[idx++] = t;
					done[t] = true;
					st.pop();
				}
			}
		}
}
 
int fallingSide(int idx)
{
	if(Y1[idx] > Y2[idx])
		return X2[idx];
	else
		return X1[idx];
}
 
double getY(int idx, int x)
{
	if(X1[idx] == x)
		return Y1[idx];
	else if(X2[idx] == x)
		return Y2[idx];
	double result = (Y2[idx] - Y1[idx]);
	result /= (X2[idx] - X1[idx]);
	result *= (x - X1[idx]);
	result += Y1[idx];
	return result;
}
 
int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i ++)
	{
		scanf("%d %d %d %d", X1 + i, Y1 + i, X2 + i, Y2 + i);
		v.push_back(P(X1[i], i, Y1[i], 1));
		v.push_back(P(X2[i], i + 1000000, Y2[i], 0));
	}
	sort(v.begin(), v.end());
	memset(pure, 0, sizeof pure);
 
	set<int> st;
 
	int LastMax = -1;
	for(int i = 0; i < v.size(); i ++)
	{
		// 1. update LastMax's pure
		if(LastMax != -1)
			pure[LastMax] += v[i].first - v[i-1].first;
 
		// 2. append or remove the current item
		if(v[i].second >= 1000000)
		{
			st.erase(v[i].second - 1000000);
			v[i].second -= 1000000;
		}
		else
			st.insert(v[i].second);
 
		double myY = getY(v[i].second, v[i].first);
 
		int itemBelow = -1;
		double itemBelowY = 0;
		LastMax = -1;
		double LastMaxY = 0;
		// 3. Find the one below current item and update the LastMax
		for(set<int>::iterator it = st.begin(); it != st.end(); it ++)
		{
			double Y = getY(*it, v[i].first);
			if(LastMax == -1 || LastMaxY < Y)
			{
				LastMax = *it;
				LastMaxY = Y;
			}
			if(*it != v[i].second)
				if(Y < myY)
					if(itemBelow == -1 || itemBelowY < Y)
					{
						itemBelow = *it;
						itemBelowY = Y;
					}
		}
 
		// 4. Update the graph if on the falling side
		if(itemBelow != -1 && fallingSide(v[i].second) == v[i].first)
		{
			graph[itemBelow].push_back(v[i].second);
			//~ cout << v[i].second << " to " << itemBelow << endl;
		}
	}
 
	topologicalSort();
 
	for(int i = 0; i < n; i ++)
	{
		int t = order[i];
		for(int j = 0; j < graph[t].size(); j ++)
			pure[t] += pure[graph[t][j]];
	}
 
	for(int i = 0; i < n; i ++)
		cout << pure[i] << endl;
 
	return 0;
}