Pagini recente » Cod sursa (job #2356184) | Cod sursa (job #334685) | Cod sursa (job #2636725) | Cod sursa (job #727825) | Cod sursa (job #2572614)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120009;
const int INF = 1<<30;
struct punct{
double x,y;
}a[NMAX];
int n;
void Read()
{
int i;
fin>>n;
for(i = 1; i<=n; ++i)
fin>>a[i].x>>a[i].y;
}
bool orient(punct A, punct B, punct C)
{
return (A.y - B.y) * (B.x - C.x) < (A.x - B.x) * (B.y - C.y);
}
bool comp(punct A, punct B)
{
return orient(a[1], A, B);
}
void Do()
{
int i,j;
int xmin = INF, ymin = INF, idx;
idx = 1;
xmin = a[1].x;
ymin = a[1].y;
punct A,B;
vector<int> S;
for(i = 1; i<=n; ++i)
{
if(a[i].y < ymin)
{
xmin = a[i].x ;
ymin = a[i].y ;
idx = i;
}
else if(a[i].y == ymin && a[i].x < xmin)
{
xmin = a[i].x ;
ymin = a[i].y ;
idx = i;
}
}
swap(a[1], a[idx]);
sort(a+2, a+n+1, comp);
S.push_back(1);
S.push_back(2);
for(i = 3; i<=n; ++i)
{
while(S.size()>=2 && !orient(a[S[S.size()-2]], a[S[S.size()-1]], a[i] ))
S.pop_back();
S.push_back(i);
}
fout<<S.size()<<"\n";
for(i = 0; i<S.size(); ++i)
fout<<fixed<<setprecision(6)<<a[S[i]].x<<" "<<a[S[i]].y<<"\n";
}
int main()
{
Read();
Do();
return 0;
}