Cod sursa(job #541998)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 25 februarie 2011 17:32:46
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <algorithm>
#define N 120001

using namespace std;
int n;
int top;
int top2;
int stack[N];
int stackd[N];
struct Punct {
    double x;
    double y;
};
Punct sir[N];
bool cmp(Punct i, Punct j) {
    return i.x < j.x;

}
bool cmpy(Punct i, Punct j) {
    return i.y < j.y;

}
int CrossProd(int i, int j, int k)
{
    return (((sir[j].x - sir[i].x) * (sir[k].y - sir[i].y) - (sir[k].x - sir[i].x) * (sir[j].y - sir[i].y)) <= 0);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        double xp,yp;
        scanf("%lf %lf",&xp,&yp);
        sir[i].x = xp;
        sir[i].y = yp;
    }
    sort(sir + 1, sir + n + 1, cmp);
    int i = 1;
    while (i <= n) {
        int j = i;
        while (sir[j].x == sir[j+1].x && j < n) j++;
        if (j != i) {
            sort(sir + i, sir + j, cmpy);
        }
        i = j + 1;
    }
    stack[1] = 1;
    stack[2] = 2;
    top = 2;
    for(int i = 3; i <= n; i++) {
        while (CrossProd(stack[top], i, stack[top - 1]) == 0) top--;
        stack[++top] = i;
    }
    stackd[1] = n;
    stackd[2] = n - 1;
    top2 = 2;
    for(int i = n - 2; i > 0; i--) {
        while (CrossProd(stackd[top2], i, stackd[top2 - 1]) == 0) top2--;
        stackd[++top2] = i;
    }
    printf("%d\n",top + top2 - 2);
    for(int i = top; i > 0; i--)
     printf("%lf %lf\n",sir[stack[i]].x, sir[stack[i]].y);
    for(int i = top2 - 1; i > 1; i--)
     printf("%lf %lf\n",sir[stackd[i]].x, sir[stackd[i]].y);
    return 0;
}