Pagini recente » Cod sursa (job #11082) | Cod sursa (job #2103781) | Cod sursa (job #2147800) | Cod sursa (job #2421110) | Cod sursa (job #2778171)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
long double x, y;
}p[120000], stiva[120000];
int TheChosenOne, n, ns;
long double determinant(punct a, punct b, punct c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
void read()
{
fin>>n;
for(int i=0; i<n; i++)
{
fin>>p[i].x>>p[i].y;
if(p[i].x<p[TheChosenOne].x)
TheChosenOne=i;
if(p[i].x==p[TheChosenOne].x)
if(p[i].y<p[TheChosenOne].y)
TheChosenOne=i;
}
swap(p[0], p[TheChosenOne]);
}
bool custom(punct a, punct b)
{
return determinant(p[0], a, b)>0;
}
void LeSorteAuChocolat()
{
sort(p, p+n, custom);
// for(int i=0; i<n; i++)
// cout<<p[i].x<<" "<<p[i].y<<'\n';
}
void ActualWork()
{
stiva[0]=p[0];
stiva[1]=p[1];
ns=2;
for (int i=2; i<n; i++) {
while (determinant(stiva[ns-2], stiva[ns-1], p[i])<=0)
ns--;
stiva[ns++]=p[i];
}
}
void afisare()
{
fout<<ns<<'\n';
for(int i=1; i<ns; i++)
fout<<fixed<<setprecision(6)<<stiva[i].x <<" "<<stiva[i].y<<'\n';
fout<<fixed<<setprecision(6)<<stiva[0].x <<" "<<stiva[0].y<<'\n';
}
int main()
{
read();
LeSorteAuChocolat();
ActualWork();
afisare();
return 0;
}