Pagini recente » Cod sursa (job #1630875) | Cod sursa (job #3253517) | Cod sursa (job #2308034) | Cod sursa (job #2160706) | Cod sursa (job #1952614)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NMAX 121002
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {
double x,y;
} v[NMAX], st[NMAX];
double det(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
bool cr1(punct a, punct b){
if ( a.x == b.x )
return a.y < b.y;
return a.x < b.x;
}
bool cr2(punct a, punct b){
return det (v[1], a, b) < 0;
}
int n,k;
int main(){
f >> n;
for (int i = 1; i <= n; i++)
f >> v[i].x >> v[i].y;
sort(v+1,v+n+1,cr1);
sort(v+2,v+n+1,cr2);
st[1]=v[1];
st[2]=v[2];
st[3]=v[3];
k=3;
for (int i=4; i<=n; ++i){
while ((k >= 3) && (det(st[k],st[k-1],v[i])<0))
k--;
st[++k]=v[i];
}
g<<k<<'\n';
g<<fixed<<setprecision(12);
for (int i=k; i>=1; i--)
g<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}