Cod sursa(job #767051)

Utilizator mi5humihai draghici mi5hu Data 12 iulie 2012 17:38:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.78 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

#define MaxVal 1000000005
using namespace std;

typedef struct {
    double x, y;        
} point;

vector<point> P;
point StartP;
int N;

// counter-clockwise if ccw > 0 
// clockwise         if ccw < 0 
// ccw != 0 for this problem.
double ccw(point p1, point p2, point p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

bool myComp(point p1, point p2) {
     /*if (p1.x == StartP.x && p1.y == StartP.y) { 
         return true;
     } else if (p2.x == StartP.x && p2.y == StartP.y) {
         return false;
     }
     
     if (p1.x == StartP.x) {
         return (p2.x < StartP.x);
     } else if (p2.x == StartP.x) {
         return (p1.x > StartP.x);      
     }
     
     double tg1 = (p1.y - StartP.y) / (p1.x - StartP.x);
     double tg2 = (p2.y - StartP.y) / (p2.x - StartP.x);
     if ((tg1 > 0 && tg2 > 0) || (tg1 < 0 && tg2 < 0)) {
        return (tg1 < tg2);          
     } else if (tg1 < 0)  {
        return false; // p2, p1      
     } else {
        return true;  // p1, p2       
     }*/
     return (ccw(StartP, p1, p2) > 0);
}

void print_vec(int M) {
     vector<point>::iterator it;
     point St = *(P.begin());
     printf("%d\n", M);
     for (it = P.begin(); it != P.end(); it++) {
         if ((*it).x == St.x && (*it).y == St.y && it != P.begin()) {
             break;
         }
         printf("%lf %lf\n",(*it).x, (*it).y); 
     }    
}

void sw(int poz1, int poz2) {
     point aux;
     aux = P[poz1];
     P[poz1] = P[poz2];
     P[poz2] = aux;     
}

void Graham_Scan() {
     int M = 1;
     P.push_back(StartP);
     
     
     for (int i = 2; i <= N; i++) {
           while (ccw(P[M-1], P[M], P[i]) <= 0) {
               if (M > 1) {
                   M--;       
               } else if (i == N){
                   break;
               } else {
                   i++;       
               }       
           }
           M++;
           sw(i, M);
     }
     
     print_vec(M);
}

point new_point(double a, double b) {
      point p;
      p.x = a;
      p.y = b;
      return p;      
}

void read_() {     
     scanf("%d", &N);
     StartP.x = MaxVal;
     StartP.y = MaxVal;
     for (int i = 0; i < N; i++) {
         double a, b;
         scanf("%lf%lf", &a, &b);
         point crt = new_point(a, b);
         if (b < StartP.y || (b == StartP.y && a < StartP.x)) {
             StartP = crt; 
         } 
         P.push_back(crt);         
     }    
     sort(P.begin(), P.end(), myComp);      
}

int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    
    read_();    
    Graham_Scan();
    
    return 0;
}