Pagini recente » Cod sursa (job #340164) | Cod sursa (job #1794569) | Cod sursa (job #2123206) | Cod sursa (job #2255121) | Cod sursa (job #3159145)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct pct{
double x,y;
}a[120001];
vector<pct> s;
vector<pct> q;
bool comp1(pct d,pct c)
{
if(d.x==c.x)
return d.y<c.y;
else return d.x<c.x;
}
bool comp2(pct d,pct c)
{
if(d.x==c.x)
return d.y>c.y;
else return d.x>c.x;
}
void citire()
{
fin>>n;
for(int i=0;i<n;i++)
fin>>a[i].x>>a[i].y;
}
int det(pct q,pct w,pct e)
{
double l=(q.x*w.y)+(w.x*e.y)+(e.x*q.y)-(w.y*e.x)-(e.y*q.x)-(q.y*w.x);
return l>0;
}
void inv1()
{
for(int i=2;i<n;i++)
{
while(s.size() >= 2 && det(s[s.size()-2],s[s.size()-1],a[i]))
{
s.pop_back();
}
s.push_back(a[i]);
}
}
void inv2()
{
for(int i=n-3;i>=0;i--)
{
while(q.size() >= 2 && det(q[q.size()-2],q[q.size()-1],a[i]))
{
q.pop_back();
}
q.push_back(a[i]);
}
}
int main()
{
citire();
sort(a,a+n-1,comp1);
s.push_back(a[0]);
s.push_back(a[1]);
q.push_back(a[n-1]);
q.push_back(a[n-2]);
inv1();
inv2();
fout<<s.size()+q.size()-2<<endl;
for(int i=q.size()-2;i>=0;i--)
fout<<fixed<<setprecision(6)<<q[i].x<<" "<<q[i].y<<endl;
for(int i=s.size()-2;i>=0;i--)
fout<<fixed<<setprecision(6)<<s[i].x<<" "<<s[i].y<<endl;
return 0;
}