Pagini recente » Cod sursa (job #2310861) | Cod sursa (job #981804) | Cod sursa (job #3000949) | Cod sursa (job #1362957) | Cod sursa (job #2371362)
#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;
}
}
}
int Orientare(point k, point l, point m)
{
int o1=(k.y-l.y)*(l.x-m.x);
int o2=(l.y-m.y)*(k.x-l.x);
if(o1==o2)
return 0;
if(o1>o2)
return -1;
return 1;
}
bool comp(point A, point B)
{
return (Orientare(a[start],A,B)==1);
}
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);
for(i=3; i<=n; ++i)
{
while(Orientare(a[S.size()-2], a[S.back()], a[i] )==-1)
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;
}