Pagini recente » Cod sursa (job #3003163) | Cod sursa (job #274504) | Cod sursa (job #3233079) | Cod sursa (job #2208176) | Cod sursa (job #1452983)
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct pp
{
double x,y;
};
pp v[120001];
int m = 1;
bool ccw(pp a, pp b, pp c)
{
if ( (b.x-a.x)*(c.y-a.y) - (b.y - a.y)*(c.x - a.x) >= 0) return true;
else return false;
}
bool comp(pp b, pp c)
{
return ( (b.y-v[0].y)*(c.x - v[0].x)) < (b.x - v[0].x)*(c.y-v[0].y );
}
int main()
{
fin>>n;
v[0].x=0;
v[0].y=0;
for (int i=0; i<n; i++)
{
pp x;
fin>>x.x>>x.y;
v[i+1]=x;
}
for (int i=1; i<=n; i++)
if (v[i].y<=v[m].y)
{
if (v[i].y == v[m].y && v[i].x<v[m].x) m=i;
else if (v[i].y != v[m].y) m=i;
}
swap(v[m],v[1]);
v[0] = v[1];
sort(v+2,v+n+1,comp);
int a=1;
for (int i=2; i<=n; i++)
{
while(!ccw(v[a-1],v[a],v[i]))
if (a>1) a--;
else if (i==n) break;
else i++;
a++;
swap(v[i],v[a]);
}
fout<<a<<'\n';
for (int i=1; i<=a; i++)
fout<<setprecision(9)<<fixed<<v[i].x<<' '<<v[i].y<<'\n';
return 0;
}