Solution to tw-icpc-blog weekly farm 30

CF[gRkn7bDfsN-212807]-D.cpp

/*
 * Solution idea: 
 * - Sort points around the origin clockwise.
 * - Then choose a start point and check if the contraints are satisfied. 
 */
#include <bits/stdc++.h>
using namespace std;
/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______      
 * |\  \|\  \  |\  ___ \  |\  ___ \     
 * \ \  \/  /|_\ \   __/| \ \   __/|    
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__  
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \ 
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

struct PT { 
	long long x, y;
	PT() {}
	PT(long long x, long long y) : x(x), y(y) {}
	PT(const PT &p) : x(p.x), y(p.y)    {}
	PT operator + (const PT &p)  const { return PT(x+p.x, y+p.y); }
	PT operator - (const PT &p)  const { return PT(x-p.x, y-p.y); }
	PT operator * (long long c)     const { return PT(x*c,   y*c  ); }
	PT operator / (long long c)     const { return PT(x/c,   y/c  ); }
	bool operator<(const PT &p)  const { return make_pair(x,y)<make_pair(p.x,p.y); }
	bool operator==(const PT &p)  const { return !(*this < p) && !(p < *this); }
};
long long dot(PT p, PT q)     { return p.x*q.x+p.y*q.y; }
long long dist2(PT p, PT q)   { return dot(p-q,p-q); }
long long cross(PT p, PT q)   { return p.x*q.y-p.y*q.x; }
PT norm(PT x, long long l)    { return x * sqrt(l*l / dot(x,x));}
istream &operator>>(istream &is, PT &p) {return is >> p.x >> p.y; }
ostream &operator<<(ostream &os, const PT &p) {return os << "(" << p.x << "," << p.y << ")";}

PT center;
bool cmp(PT a, PT b) {
	if(a.x == center.x && a.y == center.y)
		return false;
	if(b.x == center.x && b.y == center.y)
		return true;

	if (a.x >= center.x  && b.x < center.x)
		return true;
	if (a.x < center.x && b.x >= center.x)
		return false;
	if (a.x - center.x == 0 && b.x - center.x == 0) {
		if (a.y - center.y >= 0 || b.y - center.y >= 0)
			return a.y > b.y;
		return b.y > a.y;
	}

	// compute the cross product of vectors (center -> a) x (center -> b)
	return cross(a-center,b-center) < 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin>>N;
	vector<PT> v(N);
	for(int i = 0;i < N;i++)
		cin>>v[i];
	center = {0,0};
	sort(v.begin(),v.end(),cmp);
	//	v.push_back(v[0]);
	int st = -1;
	for(int s = 0;s < N;s++) {
		bool can = true;
		for(int d = 0;d+1 < N && can;d++) {
			//		cerr<<v[i]<<'\n';
			int i = (s + d)%N;
			can &= dot(v[i],v[(i+1)%N]) > 0 && cross(v[i],v[(i+1)%N]) <=0;
		}
		if(can) {
			st = s;
			break;
		}
	}
	if(st == -1) cout<<"-1\n";
	else for(int i = 0;i < N;i++) cout<<v[(st+i)%N].x<<' '<<v[(st+i)%N].y<<'\n';
	return 0;
}