Pagini recente » Cod sursa (job #2831594) | Cod sursa (job #2883035) | Cod sursa (job #554971) | Monitorul de evaluare | Cod sursa (job #1920042)
#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 p1, point p2, point p3){
return (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.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;
}