Pagini recente » Cod sursa (job #1513923) | Cod sursa (job #787408) | Cod sursa (job #1455391) | Cod sursa (job #841393) | Cod sursa (job #2371442)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int xs,ys,n;
int start;
struct point
{
double x,y;
}a[123000],S[123000];
void Read()
{
int i;
double xmin=1000000003;
double ymin= 1000000003;
fin>>n;
for(i=1; i<=n; ++i)
{
fin>>a[i].x>>a[i].y;
if(ymin>a[i].y)
{
start=i;
xmin=a[i].x;
ymin=a[i].y;
}
else if(ymin==a[i].y && xmin>a[i].x)
{
start=i;
xmin=a[i].x;
ymin=a[i].y;
}
}
}
bool Orientare(point k, point l, point m)
{
long double o1=1LL*(k.y-l.y)*(l.x-m.x);
long double o2=1LL*(l.y-m.y)*(k.x-l.x);
return (o1<=o2);
}
bool comp(point A, point B)
{
return (Orientare(a[start],A,B));
}
void Do()
{
int i,j;
swap(a[1],a[start]);
sort(a+2,a+n+1,comp);
//cout<<Orientare(a[1],a[2],a[3]);
vector<int> S;
S.push_back(1);
S.push_back(2);
S.push_back(3);
for(i=4; i<=n; ++i)
{
while(!Orientare(a[S.size()-2], a[S.back()], 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;
}