Pagini recente » Cod sursa (job #2631793) | Cod sursa (job #3040785) | Cod sursa (job #2612181) | Cod sursa (job #2375210) | Cod sursa (job #795176)
Cod sursa(job #795176)
#include <cstdio>
#include <algorithm>
#define inf 0xfffffff
using namespace std;
struct point{
double x, y;
bool operator < (point const &b) const{
return x > b.x || x == b.x && y < b.y;
}
} P[120001] , st[120001];
int N, top = -1;
double Intoarcere(point &A, point &B, point &C){
return (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / 2;
}
double Sloap(point A, point B){
if (B.x == A.x) return -inf;
return (B.y - A.y)/(B.x - A.x);
}
double Cmp (point A, point B){
return Sloap(P[0], A) < Sloap(P[0], B);
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i;
scanf("%d", &N);
for (i = 0; i < N; i++) scanf("%lf %lf",&P[i].x,&P[i].y);
sort(P, P + N);
sort(P + 1, P + N, Cmp);
for (i = 0; i < N; i++){
while (top > 1 && Intoarcere(st[top-1], st[top], P[i]) < 0) top--;
st[++top] = P[i];
}
printf("%d\n", top + 1);
for (i = 0; i <= top; i++) printf("%lf %lf\n", st[i].x, st[i].y);
}