Pagini recente » Cod sursa (job #1925543) | Cod sursa (job #2471369) | Cod sursa (job #2003790) | Cod sursa (job #1399544) | Cod sursa (job #1920120)
#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 (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(point a,point b)
{
return det(p[1],a,b)<0;
}
int main()
{
f >> n;
int ind;
point mn;
f>>mn.x>>mn.y;
p[1].x=mn.x;
p[1].y=mn.y;
for(int i=2;i<=n;i++)
{
f>>p[i].x>>p[i].y;
if(mn.x>p[i].x || (mn.x==p[i].x && mn.y>p[i].y))
{
mn=p[i];
ind=i;
}
}
swap(p[ind],p[1]);
sort(p+2,p+n+1,cmp);
int top=2;
st[1]=p[1];
st[2]=p[2];
for(int i=3;i<=n;i++)
{
while(top>=2 && det(p[i],st[top-1],st[top])>0)
top--;
st[++top]=p[i];
}
g << fixed << setprecision(6) <<top << "\n";
for(int i=top;i>=0;i--)
g << st[i].x << " " << st[i].y << "\n";
return 0;
}