Pagini recente » Cod sursa (job #2222528) | Cod sursa (job #2756302) | Cod sursa (job #2796757) | Cod sursa (job #1934555) | Cod sursa (job #1382318)
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdio>
using namespace std;
#define NMAX 120001
#define EPS 1e-12
unsigned long n,h;
struct punct
{
double x,y;
}v[NMAX];
unsigned s[NMAX],ok[NMAX];
int semn(punct &a, punct &b, punct &c)
{
double det=a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
if (det==0) return 0;
return (det<0)?(-1):1;
}
int cmp1(double a, double b)
{
if (a+EPS<b) return 1;
if (b+EPS<a) return -1;
return 0;
}
int cmp(punct a, punct b)
{
int t;
t=cmp1(a.x,b.x);
if (t!=0) return t==1;
return (cmp1(a.y,b.y)==1);
}
void citire()
{
ifstream f("infasuratoare.in");
f>>n;
for (unsigned long i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
}
void rezolvare()
{
s[1]=1; s[2]=2; ok[2]=1;
long nr_el_stiva=2,nr_pc_infas=1,i=3,contor=1;
while(!ok[1])
{
while (ok[i])
{
if (i==n) contor=-1;
i+=contor;
}
while (nr_el_stiva>=2 && semn(v[s[nr_el_stiva-1]],v[s[nr_el_stiva]],v[i])==-1)
ok[s[nr_el_stiva--]]=0;
s[++nr_el_stiva]=i;
ok[i]=1;
}
h=nr_el_stiva-1;
}
int main()
{
freopen("infasuratoare.out","w",stdout);
citire();
rezolvare();
printf("%u\n",h);
for (unsigned long i=1;i<=h;i++)
printf("%f %f\n", v[s[i]].x, v[s[i]].y);
return 0;
}