polygons

gistfile1.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
long long int absolute(int a){
	long long int f = (long long int)a < 0 ? -a : a;
	return f;
}
 
 
class polygon{
 
public:
	int id;
	long long int polyArea;
	polygon(vector< pair<int, int> > points, int id){
 
		vector<int> xes;
		vector<int> ys;
 
		int size = points.size();
 
		for (int i = 0; i < size; i++){
			xes.push_back(points[i].first);
			ys.push_back(points[i].second);
		}
 
		this->id = id;
 
		//TODO : Compute area for polygon
		unsigned long long int area = 0;
		int j = size - 1;
 
		for (int i = 0; i < size; i++){
			area += absolute(((xes[j] + xes[i])  * (ys[j] - ys[i]))) / 2;
			j = i;
		}
		polyArea = area;
	}
};
 
struct less_than_key
{
	inline bool operator() (const polygon* struct1, const polygon* struct2)
	{
		return (struct1->polyArea < struct2->polyArea);
	}
};
 
 
 
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
 
		vector<polygon*> p;
 
		for (int i = 0; i < n; i++){
			int m;
			cin >> m;
			vector< pair<int, int> > v;
 
			for (int j = 0; j < m; j++){
				int f, s;
				cin >> f >> s;
				v.push_back(pair <int, int>(f, s));
			}
 
			polygon* ps = new polygon(v, i);
			p.push_back(ps);
		}
 
		//sort based on area
		sort(p.begin(), p.end(), less_than_key());
 
		map<int, int> ans;
 
		//since they are sorted by area
		//this means that the element at index zero must have 0 
		//polygons inside it thus 
		//we map it's id to the count of polygons.
		//(n - 1)-th element will contain n - 1 polygons inside it.
 
		for (int i = 0; i < n; i++){
			ans[p[i]->id] = i;
		}
 
		for (int i = 0; i < n; i++)
			cout << ans[i] << " ";
 
		cout << endl;
	}
	return 0;
}