Pagini recente » Cod sursa (job #1948967) | Cod sursa (job #1229396) | Cod sursa (job #373208) | Cod sursa (job #2577589) | Cod sursa (job #1920072)
#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);
}
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 || (p[i].x==p[Min].x && p[Min].y>p[i].y))
Min=i;
}
swap(p[Min],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=1;i<=top;i++)
g << st[i].x << " " << st[i].y << "\n";
return 0;
}