Pagini recente » Cod sursa (job #2958502) | Cod sursa (job #2975250) | Cod sursa (job #968336) | Cod sursa (job #1393526) | Cod sursa (job #1051278)
//
// 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>
#include <algorithm>
typedef struct pct {
double x, y;
} point;
point pts[MAX];
int swap(point *p1, point *p2)
{
point p = *p1;
*p1 = *p2;
*p2 = p;
return 0;
}
double delta(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)
{
return (delta(pts[0], p1, p2) < 0);
}
int main(int argc, const char * argv[])
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
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);
std::sort(pts + 1, pts + n, cmp);
S[0] = 0;
S[1] = 1;
int N = 1;
for(i = 2; i < n; i++)
{
while(delta(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;
}