Pagini recente » Cod sursa (job #639646) | Cod sursa (job #1492842) | Cod sursa (job #1790612) | Cod sursa (job #2369882) | Cod sursa (job #2370025)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
long double x, y;
}p[120005];
int n, k;
int sol[120005];
long double det(point a, point b, point c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}
bool cmp(point &a, point &b)
{
return det(a, b, p[1])<0;
}
int main()
{
fin>>n;
fin>>p[1].x>>p[1].y;
for(int i=2; i<=n; ++i)
{
fin>>p[i].x>>p[i].y;
if(p[i].x<p[1].x)
{
swap(p[1], p[i]);
continue;
}
if(p[i].x==p[1].x && p[i].y<p[1].y)
{
swap(p[1], p[i]);
continue;
}
}
sort(p+2, p+n+1, cmp);
k=0;
sol[++k]=1;
for(int i=2; i<=n; ++i)
{
while(k>=2 && det(p[sol[k-1]], p[sol[k]], p[i])>0) --k;
sol[++k]=i;
}
fout<<k<<"\n";
for(int i=k; i>=1; --i)
{
fout<<fixed<<setprecision(6)<<p[sol[i]].x<<" "<<p[sol[i]].y<<"\n";
}
return 0;
}