Cod sursa(job #847935)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 4 ianuarie 2013 17:41:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

#ifndef M_PI
#define M_PI 3.141592654
#endif

typedef struct Point{
    double x;
    double y;
    double angle;
}Point;

double get_angle(double x1, double y1, double x2, double y2)
{
    if( x1 == x2 )
        return M_PI/2;
    else
        return atan((y2-y1)/(x2-x1));
}

double get_angle(Point p1, Point p2)
{
    return get_angle(p1.x,p1.y,p2.x,p2.y);
}

//////////// STACK //////////////////////

typedef struct tagNode
{
    Point value;
    struct tagNode *next;
}Node;

struct Stack
{
    Node* start;

    Stack(){
        this->start = NULL;
    }

    void push(Point value){
        Node *niu = new Node;
        niu->next = this->start;
        niu->value = value;
        this->start = niu;
    }

    Point top(){
        return this->start->value;
    }

    void pop(){
        Node* toDelete = this->start;
        this->start = this->start->next;
        delete toDelete;
    }

    int isEmptyStack(){
        return this->start == NULL;
    }
};

////////////////////////////////////////

#define MAXN 120000

int N;
Point points[MAXN];

Stack solution;
int count;

int compare(const void *pt1, const void *pt2)
{
    return ((Point*)pt1)->angle < ((Point*)pt2)->angle;
}

int main(int argc, char* argv[])
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&N);
    int startPos = 0;

    int i;
    for(i=0;i<N;i++){
        scanf("%lf %lf",&points[i].x,&points[i].y);
        if( (points[i].x < points[startPos].x) ||
            (points[i].x == points[startPos].x && points[i].y < points[startPos].y))
            startPos = i;
    }

    Point aux = points[startPos];
    points[startPos] = points[0];
    points[0] = aux;

    for(i=1;i<N;i++){
        points[i].angle = get_angle(points[0],points[i]);
    }

    qsort(points+1,N-1,sizeof(Point),compare);

    solution.push(points[0]);
    solution.push(points[1]);
    count = 2;

    for(i=2;i<N;i++){
#define p1 (solution.start->next->value)
#define p2 (solution.start->value)
#define p3 (points[i])
        while( (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x) > 0 ){
            solution.pop();
            count--;
        }

        solution.push(points[i]);
        count++;
    }
    printf("%d\n",count);
    Node* q = solution.start;
    while(q != NULL){
        printf("%lf %lf\n",q->value.x,q->value.y);
        q=q->next;
    }

    return 0;
}