Pagini recente » Cod sursa (job #1206122) | Cod sursa (job #126372) | Cod sursa (job #3149725) | Cod sursa (job #1981958) | Cod sursa (job #2535730)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
bool operator <(const punct& other) const
{
if(x == other.x)
return (y < other.y);
return x < other.x;
}
};
int n;
vector <punct> v;
punct a[120005],b[120005];
void citire()
{
fin>>n;
v.resize(n);
for(int i=0; i<n; i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v.begin(),v.end());
}
int det(punct a,punct b,punct c)
{
return ((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)>0);
}
void infasuratoare()
{
a[0]=v[0];
a[1]=v[1];
int k=2;
for(int i=2; i<n; i++)
{
while(k > 1 && det(a[k-2],a[k-1],v[i])==0)
k--;
a[k++]=v[i];
}
b[0]=v[n-1];
b[1]=v[n-2];
int aux=2;
for(int i=n-3; i>=0; i--)
{
while(aux>1&&det(b[aux-2],b[aux-1],v[i])==0)
aux--;
b[aux++]=v[i];
}
fout<<k+aux-2<<"\n";
for(int i=0; i<k-1; i++)
{
fout<<setprecision(6)<<fixed;
fout<<a[i].x<<" "<<a[i].y<<"\n";
}
for(int i=0; i<aux-1; i++)
{
fout<<setprecision(6)<<fixed;
fout<<b[i].x<<" "<<b[i].y<<"\n";
}
}
int main()
{
citire();
infasuratoare();
return 0;
}