Pagini recente » Cod sursa (job #2804647) | Cod sursa (job #2421623) | Cod sursa (job #2273401) | Cod sursa (job #92026) | Cod sursa (job #2988408)
#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;
// sau return (A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x);
}
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;
}