Pagini recente » Cod sursa (job #1275130) | Cod sursa (job #356933) | Cod sursa (job #1832244) | Cod sursa (job #2100612) | Cod sursa (job #2254534)
#include <bits/stdc++.h>
using namespace std;
const int nmax=120005;
const double eps=0.000000000001;
pair<double,double> v[nmax];
stack<int>st;
stack<int>afis;
bool f[nmax];
bool is_st(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
if((c.second*(b.first-a.first)+c.first*(a.second-b.second)+b.second*a.first-a.second*b.first)<eps)
return 1;
return 0;
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>v[i].second>>v[i].first;
sort(v+1,v+n+1);
st.push(1);
st.push(2);
f[2]=true;
int sign=1;
for(int i=3; i; i+=sign)
{
if(f[i]==true)
continue;
int a,b;
while(st.size()>1)
{
f[st.top()] = false;
b=st.top();
st.pop();
a=st.top();
if(is_st(v[a],v[b],v[i]))
{
st.push(b);
f[st.top()] = true;
break;
}
}
st.push(i);
f[st.top()] = true;
if(st.top()==n)
sign=-1;
}
st.pop();
while(!st.empty())
{
afis.push(st.top());
st.pop();
}
cout<<afis.size()<<"\n";
cout << setprecision(12) << fixed;
while(!afis.empty())
{
int t=afis.top();
cout<<v[t].second<<" "<<v[t].first<<"\n";
afis.pop();
}
return 0;
}