Cod sursa(job #1358395)

Utilizator petiVass Peter peti Data 24 februarie 2015 16:30:40
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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(const p &p1,const p &p2,const 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;

    p v[120005]; //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)
            c=i;
    }

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

    int s[120005]; 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";
    }
}