Pagini recente » Cod sursa (job #772492) | Cod sursa (job #2090938) | Cod sursa (job #1548227) | Cod sursa (job #841590) | Cod sursa (job #407313)
Cod sursa(job #407313)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 120010
struct pct{
double x, y;};
pct v[NMAX];
int n, st[NMAX], f[NMAX];
struct cmp{
bool operator()(const pct &a,const pct &b){
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
};
int semn(pct a, pct b, pct c){
double r = a.x*(b.y - c.y) + b.x*( c.y - a. y) + c.x * ( a.y - b. y);
if(r > 0) return 1;
if(r < 0) return -1;
return 0;
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1, cmp());
int k = 0;
for(int i = 1; i <= n; ++i){
while(k > 1 && semn(v[st[k-1]], v[st[k]], v[i]) < 0 ){
f[st[k]] --;
k--;
}
f[i]++;
st[++k] = i;
}
for(int i = n ; i ; --i){
if(f[i]) continue;
while(k > 2 && semn(v[st[k-1]], v[st[k]], v[i]) < 0){
f[st[k]]--;
k--;
}
f[i]++;
st[++k] = i;
}
printf("%d\n", k);
for(int i = 1; i <= k; ++i)
printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
}