Pagini recente » Cod sursa (job #2817526) | Cod sursa (job #154329) | Cod sursa (job #807687) | Cod sursa (job #1076944) | Cod sursa (job #2110751)
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<vector>
#define INF 1100000000
#define DN 120100
using namespace std;
fstream fin("infasuratoare.in",ios::in),fout("infasuratoare.out",ios::out);
double x=INF,y=INF,a,b;
int n,lr=0;
class point
{
public:
double x,y;
} p[DN],r[DN];
double det(point p,point a,point b)
{
return (p.x*a.y+a.x*b.y+p.y*b.x-p.y*a.x-a.y*b.x-b.y*p.x);
}
bool cmp(point a,point b)
{
return det(p[0],a,b)>=0;
}
int main()
{
int i,ind;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a>>b;
if(x>a || (x==a && y>b))
{
x=a;y=b;ind=i;
}
p[i]={a,b};
}
p[0]=p[ind];p[ind]=p[n];
sort(p+1,p+n,cmp);
r[1]=p[0];lr=1;
for(i=1;i<n;i++)
{
while(lr>1 && det(r[lr-1],r[lr],p[i])<0) lr--;
r[++lr]=p[i];
}
fout<<lr<<"\n";
for(i=1;i<=lr;i++) fout<<fixed<<setprecision(12)<<r[i].x<<" "<<r[i].y<<"\n";
}