Pagini recente » Cod sursa (job #151214) | Cod sursa (job #307930) | Cod sursa (job #665664) | Cod sursa (job #1203624) | Cod sursa (job #2988396)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point{
double x, y;
}v[120100], st[120100];
int n, vf;
double det(point A,point B, point C)
{
return A.x*B.y+ C.x*A.y + B.x*C.y - C.x*B.y - A.x*C.y - B.x*A.y;
}
int comp1(point A,point B)
{
if(A.x==B.x) return (A.y<B.y);
else return (A.x<B.x);
}
int comp2(point B,point C)
{
return (det(v[1],B,C)<0);
}
int main()
{
int i;
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,comp1);
st[1]=v[1];
sort(v+2,v+n+1,comp2);
st[2]=v[2];
vf = 2;
for(i=3;i<=n;i++)
{
while(vf>2 && det(st[vf-1],st[vf],v[i])>0) vf--;
st[++vf]=v[i];
}
g<<vf<<'\n';
for(i=vf;i>=1;i--)
g<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<" "<<'\n';
return 0;
}