Pagini recente » Cod sursa (job #2875681) | Cod sursa (job #27006) | Cod sursa (job #2756140) | Cod sursa (job #2736392) | Cod sursa (job #1915715)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
pair < double,double > v[120005];
stack < int > st;
bool seen[120005],ok;
int x,n,i;
int det(pair < int,int > a,pair < int,int > b,pair < int,int > c)
{
return b.second*c.first + c.second*a.first + a.second*b.first - a.first*b.second - b.first*c.second - c.first*a.second;
}
int main()
{
f >> n;
for(i = 1; i <= n; i++)
f >> v[i].second >> v[i].first;
sort(v + 1,v + n + 1);
st.push(1);
st.push(2);
seen[2] = 1;
i = 2;
while(i > 1)
{
if(not seen[i])
{
x = st.top();
st.pop();
while(st.top() != 1 && det(v[x],v[st.top()] , v[i]) < 0)
seen[x] = 0,x = st.top(),st.pop();
st.push(x);
st.push(i);
seen[i] = 1;
}
if(i == n)
ok = true;
if(not ok)
i++;
else i--;
}
n = st.size();
g << st.size() << '\n';
g << fixed << setprecision(6);
g << v[1].second << " " << v[1].first << '\n';
while(n > 1)
g << v[st.top()].second << " " << v[st.top()].first << '\n' , st.pop() ,n--;
return 0;
}