Cod sursa(job #1349306)

Utilizator petiVass Peter peti Data 20 februarie 2015 08:49:50
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct p{double x,y;};

// <0 --> CW // >0 --> CCW //==0 --> COLLINEAR
double isccw(p &p1,p &p2,p &p3){
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}

p p0;
bool cmp(p p1,p p2){
    return isccw(p0,p1,p2)>0;
}


int main(){
    ifstream ifs("infasuratoare.in");
    ofstream ofs("infasuratoare.out");

    int N;
    ifs>>N;

    vector<p> v(N);

    int c=0;
    for(int i=0;i<N;i++){
        ifs>>v[i].x>>v[i].y;

        if(v[i].x<=v[c].x)
            c=i;
    }

    p t=v[0]; v[0]=v[c]; v[c]=t;
    p0=v[0];
    sort(v.begin()+1,v.end(),cmp);

    vector<int> s(N); s[0]=0; s[1]=1;
    int top=1;

    for(int i=2;i<N;i++){
        while(top>=1 && isccw(v[s[top-1]],v[s[top]],v[i])<0)
            top--;
        s[++top]=i;
    }


    ofs<<top+1<<"\n";
    ofs<<setprecision(10);
    for(int i=0;i<=top;i++){
        ofs<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
   }
}