Cod sursa(job #1348942)

Utilizator petiVass Peter peti Data 19 februarie 2015 21:54:19
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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
int 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); //pontok


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

        if((v[i].x<v[c].x)||(v[i].x==v[c].x && v[i].y<v[c].y))
            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--;
        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";
    }
}