Pagini recente » Cod sursa (job #1360249) | Cod sursa (job #1234735) | Cod sursa (job #1397414) | Rating Vana Marc (VanaMarc) | Cod sursa (job #2145948)
#include <bits/stdc++.h>
#define Nmax 120005
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
pair < double,double > v[Nmax];
stack < int > st;
int n,i,seen[Nmax],x,semn = 1;
bool cmp(pair < double,double > a, pair < double,double > b)
{
if(a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
double arie(int x,int y,int z)
{
return v[x].first*v[y].second + v[y].first*v[z].second + v[z].first*v[x].second -
v[z].first*v[y].second - v[x].first*v[z].second - v[y].first*v[x].second;
}
int main()
{
f >> n;
for(i = 1; i <= n; i++)
f >> v[i].first >> v[i].second;
sort(v + 1,v + n + 1,cmp);
st.push(1);
st.push(2);
seen[2] = 1;
for(i = 3; i > 0; i += semn)
{
if(seen[i])
continue;
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) << v[st.top()].first << " " << v[st.top()].second << '\n';
st.pop();
}
return 0;
}