Pagini recente » Cod sursa (job #3228002) | Cod sursa (job #2785583) | Cod sursa (job #155184) | Cod sursa (job #855174) | Cod sursa (job #1464880)
#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 120005
using namespace std;
typedef struct{
double x, y;
} Punct;
int n, m, i, best;
Punct p[MAX], stack[MAX];
double ccw(const Punct& p1, const Punct& p2, const Punct& p3){
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
int compare(const Punct& r, const Punct& q){
return ccw(p[0], r, q) < 0;
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%lf%lf", &p[i].x, &p[i].y);
if(p[best].y > p[i].y)
best = i;
else if(p[best].y == p[i].y)
if(p[best].x > p[i].x)
best = i;
}
swap(p[0], p[best]);
sort(p + 1, p + n, compare);
m = 1;
stack[0] = p[0];
stack[1] = p[1];
for(i = 2; i < n; i++){
while(m >= 1 && ccw(stack[m - 1], stack[m], p[i]) > 0)
m--;
stack[++m] = p[i];
}
printf("%d\n", m + 1);
for(i = m; i >= 0; i--)
printf("%lf %lf\n", stack[i].x, stack[i].y);
return 0;
}