Skip to content

Instantly share code, notes, and snippets.

@jiunbae
Created May 16, 2015 10:01
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/3e91b09a0ee7a88620eb to your computer and use it in GitHub Desktop.
Save jiunbae/3e91b09a0ee7a88620eb to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
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+1 };
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(), [&m](POINT p, POINT q){return (p.tan-q.tan) ? p.tan < q.tan : (m.y==p.y && m.y ==q.y) ? p.x<q.x : sqrt(pow(m.y-p.y,2.) + pow(m.x -p.x,2.)) < sqrt(pow(m.y-q.y,2.)+pow(m.x-q.x,2.)) ; });
std::stack <int> stack;
vector.push_back(vector[0]);
for_each(vector.begin(), vector.end(), [&vector, &stack](POINT p){
static int cnt = 0;
if (stack.size() < 2)
stack.push(cnt);
else
{
int temp = stack.top();
POINT p2 = vector[temp]; stack.pop();
POINT p1 = vector[stack.top()]; stack.push(temp);
int point_cnt = cnt;
POINT p3 = p;
//std::cout << "compare with " << p.index << std::endl;
while ((double)(p2.x - p1.x) * (p3.y - p1.y) - (double)(p2.y - p1.y) * (p3.x - p1.x) <=0 && point_cnt < vector.size()-1)
p3 = vector[point_cnt++];
if (cnt == vector.size()-1)
{
int p = 3;
}
else if (point_cnt == vector.size()-1)
{
p3 = p;
do{
//std::cout << "point output" << vector[stack.top()].index << std::endl;
stack.pop();
int temp = stack.top();
p2 = vector[temp]; stack.pop();
p1 = vector[stack.top()]; stack.push(temp);
} while ((double)(p2.x - p1.x) * (p3.y - p1.y) - (double)(p2.y - p1.y) * (p3.x - p1.x) <= 0 && !stack.empty());
//std::cout << "point input" << vector[cnt].index << std::endl;
stack.push(cnt);
}
else if (point_cnt >cnt)
{
//std::cout << "point output" << vector[stack.top()].index << std::endl;
stack.pop();
stack.push (cnt);
//std::cout << "point input " << vector[cnt].index << std::endl;
}
else
{
if ((double)(p2.x - p1.x) / (p2.y - p1.y) == (double)(p3.x - p1.x) / (p3.y - p1.y))
{
//std::cout << "point output" << vector[stack.top()].index << std::endl;
stack.pop();
stack.push(point_cnt);
//std::cout << "point input" << vector[point_cnt].index << std::endl;
}
else
{
stack.push(point_cnt);
//std::cout << "point input" << vector[point_cnt].index << std::endl;
}
}
}
cnt++;
});
while (1)
{
int temp = stack.top();
POINT p1 = vector[temp]; stack.pop();
POINT p2 = vector[stack.top()]; stack.push(temp);
if (m.y == p1.y && p1.y == p2.y)
stack.pop();
else
break;
}
std::cout << stack.size() << std::endl;
/*while (!stack.empty())
{
std::cout << vector[stack.top()].index<< ",";
stack.pop();
}*/
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment