Cod sursa(job #868691)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 31 ianuarie 2013 14:49:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <deque>
#include <algorithm>
#include <cmath>
using namespace std;

double ar(double x1, double y1, double x2, double y2, double x3, double y3) {
    return (x2-x1)*(y3-y1) - (y2-y1) * (x3-x1);
}

struct pct{
    double x,y;
};

pct v[120001];
deque <pct> inf;
int ind,o[120001],otmp[120001];
double tg[120001],xmn,ymn;

double dist(int i, int j) {
    return sqrt( ((v[i].x-v[j].x)*(v[i].x-v[j].x)) + ((v[i].y-v[j].y)*(v[i].y-v[j].y)));
}

bool srt(int i, int j) {
    if (i==ind)
        return 1;
    else if (j==ind)
        return 0;
    else if (tg[i]==tg[j])
        return (dist(i,ind)<dist(j,ind));
    else
        return (tg[i]<tg[j]);
}
int n;
int main() {
    int i;
    xmn=ymn=2000000001;
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    in>>n;
    for (i=1; i<=n; i++) {
        in>>v[i].x>>v[i].y;
        v[i].x;
        v[i].y;
        if (v[i].x<xmn) {
            ind = i;
            xmn=v[i].x;
            ymn=v[i].y;
        }
        else if (v[i].x==xmn&&v[i].y<ymn) {
            ind = i;
            ymn=v[i].y;
        }

        o[i]=i;
    }

    for (i=1; i<=n; i++)
        tg[i]=atan2(v[i].y-ymn,v[i].x-xmn );

    sort(o+1,o+n+1,srt);

    ind=n;
    while (tg[o[ind]] == tg[o[ind-1]])
        ind--;
    for (i=ind; i<=n; i++)
        otmp[i]=o[n-i+ind];
    for (i=ind; i<=n; i++)
        o[i]=otmp[i];

    inf.push_back(v[o[1]]);
    inf.push_back(v[o[2]]);

    for (i=3; i<=n; i++) {
        while (inf.size()>=2 && ar( inf[inf.size()-2].x,inf[inf.size()-2].y,inf[inf.size()-1].x,inf[inf.size()-1].y,v[o[i]].x,v[o[i]].y)<0)
            inf.pop_back();
        inf.push_back(v[o[i]]);
    }

    out.precision(15);
    out<<inf.size()<<'\n';

    for (i=0; i<inf.size(); i++)
        out<<inf[i].x <<' '<<inf[i].y<<'\n';
    out.close();
    return 0;
}