Pagini recente » Cod sursa (job #1921957) | Cod sursa (job #1158255) | Cod sursa (job #1120996) | Cod sursa (job #1629047) | Cod sursa (job #2157431)
#include <bits/stdc++.h>
#define Nmax 120005
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
struct filip
{
double x,y;
} v[Nmax];
int i,n;
stack < int > st;
int seen[Nmax],semn = 1,x;
double arie(int a,int b,int c)
{
return v[a].x * v[b].y + v[b].x * v[c].y + v[c].x * v[a].y -
v[c].x * v[b].y - v[b].x * v[a].y - v[a].x * v[c].y;
}
bool cmp(filip a,filip b)
{
if(a.y < b.y)
return true;
if(a.y == b.y)
return a.x < a.y;
}
int main()
{
f >> n;
for(i = 1; i <= n; i++)
f >> v[i].x >> v[i].y;
sort(v + 1,v + n + 1, cmp);
st.push(1);
st.push(2);
seen[2] = 1;
for(i = 3; i >= 1; i += semn)
if(not seen[i])
{
x = st.top();
st.pop();
while(not st.empty() && arie(x,st.top(),i) < 0)
{
seen[x] = 0;
x = st.top();
st.pop();
}
st.push(x);
seen[i] = 1;
st.push(i);
if(i == n)
semn = -1;
}
g << st.size() - 1 << '\n';
while(st.size() > 1)
{
g << fixed << setprecision(6);
g << v[st.top()].x << " " << v[st.top()].y << '\n';
st.pop();
}
return 0;
}