Pagini recente » Cod sursa (job #237474) | Cod sursa (job #2980293) | Cod sursa (job #2319429) | Cod sursa (job #2369607) | Cod sursa (job #2110859)
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#define INF 1999999999
#define DN 120100
using namespace std;
fstream fin("infasuratoare.in",ios::in), fout("infasuratoare.out", ios::out);
struct punct{
double x,y;
} v[DN], r[DN];
int n, ind;
double mx=INF, my=INF;
int det(punct a, punct b, punct c)
{
double xx;
xx=a.x*b.y+b.x*c.y+a.y*c.x;
xx=xx-b.y*c.x-a.y*b.x-a.x*c.y;
if(xx<0) return -1;
if(xx>0) return 1;
return 0;
}
bool cmp(punct a, punct b)
{
if(det(v[1], a, b)<=0) return 1; //?
return 0;
}
int main()
{
int i,lr;
double x, y;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x>>y;
v[i]={x, y};
if(mx>x || (mx==x && my>y)){
ind=i; mx=x; my=y;
}
}
v[n+1]=v[1];
v[1]=v[ind];
v[ind]=v[n+1];
sort(v+2,v+n+1,cmp);
r[1]=v[1]; lr=1;
for(i=2;i<=n;i++)
{
while(lr>1 && det(r[lr-1], r[lr], v[i])>0) lr--;
r[++lr]=v[i];
}
fout<<fixed<<lr<<"\n";
for(i=lr;i>0;i--)
{
fout<<setprecision(12)<<r[i].x<<" "<<r[i].y<<"\n";
}
}