Posted in Math

POJ 2007

8/10/2017
Problem: http://poj.org/problem?id=2007
Solution: Sort all the points by cross product (of vectors). If v1 ^ v2 > 0,
then v1 can reach v2 rotating less than 180 degrees counter-clockwise.


#include<iostream>
#include<algorithm>
using namespace std;

struct node{
	double x, y;
	node(){}
	node(double xx, double yy):x(xx), y(yy){}
};

node n; 

bool cmp (node a, node b) {
	return (((a.x - n.x) * (b.y - n.y) - (a.y - n.y) * (b.x - n.x)) > 0);
}

int main() {
	double x, y;
	node p[105];
	int cnt = 0;
	cin >> n.x >> n.y;
	while (cin >> x >> y) {
		p[++cnt] = node(x, y);
	}
	sort(p + 1, p + cnt + 1, cmp);
	cout << "(0,0)" << endl;
	for(int i = 1; i <= cnt; i++) {
		cout << '(' << p[i].x << ',' << p[i].y << ")" << endl;
	} 
	return 0;
}