Cod sursa(job #1645678)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 10 martie 2016 13:16:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <utility>//pair
#include <algorithm>
#include <assert.h>
#include <iomanip>
#define Inf (1<<31)-1

using namespace std;
vector<pair<double,double> > v;
vector< pair<pair<double,double>, double> > nv;
pair<double,double> mini;
int N;

double abs(double x) {
    return (x<0? -x: x);
}

double tg(pair<double,double> a) {
    double x,y;
    x=(a.first - mini.first);
    y=(a.second - mini.second);
    if(x==0) {
        if (y == 0)
            return Inf;
        else
            return Inf-1;
    }
    return y/x;
}

int cmp(const pair<double,double> &a, const pair<double,double> &b) {
    double tg1, tg2;
    tg1 = tg(a);
    tg2 = tg(b);
    return tg1 > tg2;
}

void citire() {
    int i;
    double x, y;

    scanf("%d", &N);
    mini.second = Inf;
    mini.first = Inf;
    for(i=1; i<=N; i++) {
        scanf("%lf %lf", &x, &y);
        if(x<mini.first || (x == mini.first && y < mini.second))        //luam cel mai din stanga punct si facem tg adica y/x adica panta.
            mini=make_pair(x,y);
        v.push_back(make_pair(x,y));
    }
}


int left_turn (const pair<double, double> &p1, const pair<double, double> &p2, const pair<double, double> &p3) {
    /*if(p1.first == p2.first)
        return (p2.second - p1.second) * (p2.first - p3.first) > 0;
    else {
        double m = (p2.second - p1.second) / (p2.first - p1.first);
        double n = p1.second - m * p1.first;
        return (p2.first - p1.first) * (p3.second - (m * p3.first + n)) > 0;
    }*/

    return (p2.first - p1.first)*(p3.second - p1.second) - (p3.first - p1.first)*(p2.second - p1.second) ;
    return p1.first * p2.second + p2.first * p3.second + p1.second * p3.first - p3.first * p2.second - p2.first * p1.second - p1.first * p3.second;
}


int main() {
    freopen("infasuratoare.in","rt",stdin);
    freopen("infasuratoare.out","wt",stdout);
    citire();
    sort(v.begin(),v.end(),cmp);

    vector<int> S;
    S.push_back(0);
    for(int i=1; i<N; i++) {
        while(S.size() >= 2 && left_turn(v[ S[S.size()-2] ], v[S.back()], v[i]) > 0)
            S.pop_back();               //daca noul nod e mai la stanga
        S.push_back(i);                             //punctul nou
    }

    int sz = S.size();
    cout<<sz<<'\n';
    for(int i=S.size()-1; i>=0; --i) {
        //printf ("%.2lf %.2lf\n", v[emij].first, v[emij].second);
        cout<<fixed<<setprecision(6)<<v[S[i]].first<<' '<<v[S[i]].second<<'\n';
    }
    return 0;
}