Skip to content

Instantly share code, notes, and snippets.

@jiunbae
Created May 14, 2015 11:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jiunbae/3e62995c08485a77d88f to your computer and use it in GitHub Desktop.
Save jiunbae/3e62995c08485a77d88f to your computer and use it in GitHub Desktop.
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
typedef struct{
int x, y; double tan; int index;
}POINT;
int main()
{
int vertex_max;
std::cin >> vertex_max;
std::vector<POINT> vector(vertex_max , { 0, });
int min=0;
for (int vertex = 0; vertex < vertex_max; vertex++)
{
POINT p = { 0, 0, 0 ,vertex};
std::cin >> p.x >> p.y;
vector[vertex] = p;
if (vector[min].y > p.y || vector[min].y == p.y && vector[min].x < p.x)
min = vertex;
}
POINT m = vector[min];
for_each(vector.begin(), vector.end(), [&m, &vector](POINT p){static int cnt = 0; vector[cnt].tan = atan2(p.y - m.y, p.x - m.x); cnt++; });
sort(vector.begin(), vector.end(), [](POINT p, POINT q){return p.tan < q.tan; });
for (int i = 0; i < vertex_max; i++)
std::cout << vector[i].index +1<< std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment