Cod sursa(job #754725)

Utilizator visanrVisan Radu visanr Data 2 iunie 2012 23:59:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;


#define dd pair<double, double>
#define x first
#define y second
#define nmax 120010

int n, r;
dd A[nmax], st[nmax];


bool cmp(dd a, dd b)
{
     if(a.y < b.y) return true;
     if(a.y > b.y) return false;
     if(a.x < b.x) return true;
     return false;
}

int semnDet(dd a, dd b, dd c)
{
    double A = a.y - b.y, B = b.x - a.x, C = a.x * b.y - a.y * b.x;
    return (A * c.x + B * c.y + C) < 0;
}

void solve()
{
     int i;
     st[++r] = A[1];
     st[++r] = A[2];
     for(i = 3; i <= n; i++)
     {
           while(r >= 2 && semnDet(st[r - 1], st[r], A[i])) r--;
           st[++r] = A[i];
     }
     for(i = n - 1; i; i--)
     {
           while(r >= 2 && semnDet(st[r - 1], st[r], A[i])) r--;
           st[++r] = A[i];
     }
     r--;
     printf("%i\n", r);
     for(i = 1; i <= r; i++)
           printf("%lf %lf\n", st[i].x, st[i].y);
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int i;
    scanf("%i", &n);
    for(i = 1; i <= n; i++)
    {
          scanf("%lf %lf", &A[i].x, &A[i].y);
    }
    sort(A + 1, A + n + 1, cmp);
    solve();
    scanf("%i", &i);
    return 0;
}