Pagini recente » Cod sursa (job #1713293) | Cod sursa (job #1151359) | Cod sursa (job #2803167) | Cod sursa (job #3289367) | Cod sursa (job #239128)
Cod sursa(job #239128)
using namespace std;
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <cmath>
#define eps 1e-12
#define N 121000
struct nod { double x,y; nod(){}; nod(double a, double b){ x=a; y=b;};};
nod a[N];
int n;
nod P;
nod st[N];
int ns;
inline int isleft(nod p0, nod p1, nod p2)
{
double d=(p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
if(d < 0) return -1;
if(d > 0) return 1;
return 0;
}
struct cmp{
bool operator()(const nod &a, const nod &b)const
{
int t=isleft(P, a, b);
if(t == 1) return 1;
return 0;
}
};
void read()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d\n", &n);
for(int i=1;i<=n;++i) scanf("%lf %lf\n", &a[i].x, &a[i].y);
}
void solve()
{
int i;
int poz=-1;
P=nod(0x3f3f3f3f, 0x3f3f3f3f);
for(i=1;i<=n;++i)
if(a[i].y < P.y) P=a[i], poz=i;
else if(a[i].y == P.y && a[i].x < P.x) P=a[i], poz=i;
nod t=a[poz]; a[poz]=a[1]; a[1]=t;
stable_sort(a+2,a+n+1, cmp());
//for(i=1;i<=n;++i)printf("%lf %lf\n", a[i].x, a[i].y);
st[++ns]=a[1];
st[++ns]=a[2];
st[++ns]=a[3];
for(i=4;i<=n;++i)
{
while(isleft(st[ns-1], st[ns], a[i]) == -1) --ns;
st[++ns]=a[i];
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n", ns);
for(i=1;i<=ns;++i) printf("%lf %lf\n", st[i].x, st[i].y);
}
int main()
{
read();
solve();
return 0;
}