Pagini recente » Cod sursa (job #570604) | Cod sursa (job #1051273)
//
// main.cpp
// infasuratoare
//
// Created by Alexandru Bâgu on 12/9/13.
// Copyright (c) 2013 Alexandru Bâgu. All rights reserved.
//
#define MAX 120001
#include <stdio.h>
typedef struct pct {
double x, y;
} point;
int swap(point *p1, point *p2)
{
point p = *p1;
*p1 = *p2;
*p2 = p;
return 0;
}
double areasz(point p1, point p2, point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
int cmp(point p1, point p2, point p3)
{
return (areasz(p1, p2, p3) < 0);
}
int sort(point* v, int s, int d)
{
if(s >= d - 1) return 0;
int a = s, b = d, w = 1;
while(a < b)
{
if(cmp(v[0], v[a], v[b]))
{
if(w) a ++;
else b--;
}
else
{
swap(v+a, v+b);
w ^= 1;
}
}
sort(v, s, a - 1);
sort(v, a + 1, d);
return 0;
}
int main(int argc, const char * argv[])
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
point pts[MAX];
int S[MAX];
int n, i;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%lf %lf", &pts[i].x, &pts[i].y);
S[i] = 0;
}
int k = 0;
for(i = 1; i < n; i++)
if((pts[i].x < pts[k].x) || (pts[i].x == pts[k].x && pts[i].y < pts[k].y))
k = i;
swap(pts, pts + k);
sort(pts, 1, n-1);
S[0] = 0;
S[1] = 1;
int N = 1;
for(i = 2; i < n; i++)
{
while(areasz(pts[S[N-1]], pts[S[N]], pts[i]) > 0 && N >= 1) N--;
N++;
S[N] = i;
}
printf("%d \n", N+1);
for(i = N; i >= 0; i--)
printf("%lf %lf\n", pts[S[i]].x, pts[S[i]].y);
return 0;
}