Cod sursa(job #1237593)

Utilizator tavonSuleyman Magnificul tavon Data 4 octombrie 2014 13:10:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef double ld;
const int Nmax = 120002;
const ld eps = 1e-9;
const ld INF = 1e12;
struct point{
    ld x,y;
    point(){}
    point(ld _x,ld _y){
        x=_x,y=_y;
    }
} v[Nmax];
int N,S[Nmax],K;
int eq(ld a,ld b){
    return abs(a-b) < eps;
}
int smt(ld a,ld b){
    return (b-a) > eps;
}
ld sq_dist(point a,point b){
    return abs(a.x-b.x)*abs(a.x-b.x) + abs(a.y-b.y)*abs(a.y-b.y);
}
ld cp(const point &A,const point &B,const point &C){
    return A.x*B.y - A.y*B.x + B.x*C.y - B.y*C.x + C.x*A.y - C.y*A.x;
}
struct cmpA{
    inline bool operator () (const point &A,const point &B) const {
        if( eq(A.y,B.y) ) return smt(A.x,B.x);
        return smt(A.y,B.y);
    }
};
struct cmpB{
    inline bool operator () (const point &A,const point &B) const {
        if( eq( 0. , cp(v[1],A,B) ) ){
            //if( smt( cp(v[1] , point(v[1].x,INF) , A) , 0. ) ) return smt( sq_dist(v[1],A) , sq_dist(v[1],B) );
            return smt( sq_dist(v[1],B) , sq_dist(v[1],A) );
        }
        return smt( 0. , cp(v[1],A,B) );
    }
};
int main(){
    in>>N;
    ld x,y;
    for(int i=1;i<=N;i++){
        in>>x>>y;
        v[i]=point(x,y);
    }
    sort(v+1,v+N+1,cmpA());
    sort(v+2,v+N+1,cmpB());
    S[++K]=1;
    S[++K]=2;
    for(int i=3;i<=N;i++){
        while(K>2 && smt(cp(v[S[K-1]],v[S[K]],v[i]),0.)) K--;
        S[++K]=i;
    }
    S[K+1]=1;
    int n=1;
    for(int i=2;i<=K;i++){
        if( eq(0. , cp(v[abs(S[i-1])], v[S[i]], v[S[i+1]])) ) S[i]=-S[i];
        else n++;
    }
    out<<n<<'\n';
    for(int i=1;i<=K;i++) if(S[i]>0) out<<fixed<<v[S[i]].x<<' '<<v[S[i]].y<<'\n';
    return 0;
}