Cod sursa(job #475946)

Utilizator S7012MYPetru Trimbitas S7012MY Data 9 august 2010 13:45:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.94 kb
//qhull
#include <fstream>
#include <iostream>
#include <list>
#include <vector>
#include <cmath>
#include <float.h>
#define MULT 1000000000
using namespace std;

struct punct {
    double x,y;
};

int pointLocation(punct a, punct b, punct c) {
    int cp1=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    return (cp1>0) ? 1:-1;
}

double distance(punct a, punct b, punct c) {
    double abx=b.x-a.x;
    double aby=b.y-a.y;
    double num=abx*(a.y-c.y)-aby*(a.x-c.x);
    return (num>0) ? num:-num;

}

list<punct> convexHull;

void hullSet(list<punct>::iterator a, list<punct>::iterator b, list<punct> set) {
    if(set.size()==0) return;
    if(set.size()==1) {
        convexHull.insert(b,set.front());
        set.pop_front();
        return;
    }
    int dist=-MULT;
    list<punct>::iterator i,dpunct;
    for(i=set.begin(); i!=set.end(); ++i) {
        int distanta=distance((*a),(*b),(*i));
        if(distanta>dist) {
            dist=distanta;
            dpunct=i;
        }
    }
    punct p=(*dpunct);
    convexHull.insert(b,p);
    set.erase(dpunct);
    list<punct> leftSetAP,leftSetPB;
    for(i=set.begin();i!=set.end(); ++i) {
        if(pointLocation((*a),p,(*i))==1) leftSetAP.push_back(*i);
        if(pointLocation(p,(*b),(*i))==1) leftSetPB.push_back(*i);
    }
    hullSet(a,dpunct,leftSetAP);
    hullSet(dpunct,b,leftSetPB);
}

void quickhull(list<punct> puncte) {
    //list<punct> convexHull;
    //if(puncte.size()<3) return puncte;
    list<punct>::iterator minPoint, maxPoint;
    double minX=MULT;
    double maxX=-MULT;
    list<punct>::iterator i;
    for(i=puncte.begin(); i!=puncte.end(); ++i) {
        if((*i).x<minX) {
            minX=(*i).x;;
            minPoint=i;
        }
        if((*i).x>maxX) {
            maxX=(*i).x;
            maxPoint=i;
        }
    }
    punct a,b;
    a.x=(*minPoint).x;
    a.y=(*minPoint).y;
    b.x=(*maxPoint).x;
    b.y=(*maxPoint).y;
    convexHull.push_back(a);
    convexHull.push_back(b);
    puncte.erase(minPoint);
    puncte.erase(maxPoint);
    minPoint=convexHull.begin();
    maxPoint=convexHull.end();
    --maxPoint;
    list<punct> leftSet,rightSet;
    for(i=puncte.begin();i!=puncte.end(); ++i) {
        if(pointLocation(a,b,(*i)) == -1) leftSet.push_back(*i);
        else rightSet.push_back(*i);
    }
    hullSet(minPoint,maxPoint,rightSet);
    hullSet(maxPoint,minPoint,leftSet);
}

int main()
{
    ifstream f("infasuratoare.in");
    //ofstream g("infasuratoare.out");
    freopen("infasuratoare.out","w",stdout);
    int n;
    punct a;
    f>>n;
    list<punct> puncte;
    for(int i=1; i<=n; ++i) {
        f>>a.x>>a.y;
        puncte.push_back(a);
    }
    quickhull(puncte);
    printf("%d\n",convexHull.size());
    for(list<punct>::iterator i=convexHull.begin(); i!=convexHull.end(); ++i)
        printf("%.6lf %.6lf\n",(*i).x,(*i).y);
    f.close();
    //g.close();
    return 0;
}