Pagini recente » Cod sursa (job #1090237) | Cod sursa (job #2731075) | Cod sursa (job #2365341) | Cod sursa (job #2967621) | Cod sursa (job #2857728)
#define inf 0x3f3f3f3f
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <stack>
#include <queue>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct punct{
long double x, y;
}v[120001], origin;
stack<punct>s;
vector<punct>rez;
void read()
{
fin >> n;
for(int i=1; i<=n; i++)
fin >> v[i].x >> v[i].y;
}
bool valid(punct a, punct b, punct c)
{
return 1.0*(a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y)>=0;
}
long double angle(punct a)
{
long double d=1.0*(origin.x-a.x)*(origin.x-a.x)+(origin.y-a.y)*(origin.y-a.y);
if(d==0)
return 0;
return acos(1.0*(a.x-v[1].x)/sqrt(d));
}
int main()
{
read();
origin.x=inf, origin.y=inf;
for(int i=1; i<=n; i++)
{
if(origin.y>v[i].y)
origin=v[i];
if(origin.y==v[i].y && origin.x>v[i].x)
origin=v[i];
}
sort(v+1, v+n+1, [](punct a, punct b){return angle(a)<angle(b);});
s.push(v[1]), s.push(v[2]), s.push(v[3]);
int ind=4;
while(1)
{
punct c=s.top();
s.pop();
punct b=s.top();
s.pop();
punct a=s.top();
s.pop();
if(valid(a, b, c))
{
s.push(a), s.push(b), s.push(c), s.push(v[ind++]);
continue;
}
else if(s.size()==0)
s.push(a), s.push(c), s.push(v[ind++]);
else
s.push(a), s.push(c);
if(ind==n+1)
break;
}
fout << s.size() << '\n';
while(!s.empty())
rez.push_back({s.top().x, s.top().y}), s.pop();
for(auto it=rez.rbegin(); it!=rez.rend(); it=it+1)
fout << fixed << setprecision(6) << it->x << ' ' << it->y << '\n';
return 0;
}