Pagini recente » Profil MihneaGhira | Cod sursa (job #2010844) | Cod sursa (job #1490) | Cod sursa (job #3032783) | Cod sursa (job #1919986)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x,y;
}p[120010],st[120010];
int n,Min;
double det(point a,point b,point c)
{
return (a.y-b.y)*(b.x-c.x)-(b.y-c.y)*(a.x-b.x);
}
int cmp(point a,point b)
{
return det(p[1],a,b)>0;
}
int main()
{
f >> n;
Min=1;
for(int i=1;i<=n;i++)
{
f >> p[i].x >> p[i].y;
if(p[i].x<p[Min].x)
Min=i;
if(p[i].x == p[Min].x && p[i].y <p[Min].y)
Min=i;
}
swap(p[Min],p[1]);
sort(p+1,p+n+1,cmp);
p[n+1]=p[1];
int top=0;
st[++top]=p[1];
for(int i=2;i<=n;i++)
{
st[++top]=p[i];
while(top>0 && det(st[top-1],st[top],p[i+1])<0)
top--;
}
g << fixed << setprecision(6) <<top << "\n";
for(int i=1;i<=top;i++)
g << st[i].x << " " << st[i].y << "\n";
return 0;
}