Cod sursa(job #844014)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 28 decembrie 2012 18:35:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 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;
}