Pagini recente » Cod sursa (job #1806285) | Cod sursa (job #1912824) | Cod sursa (job #2021508) | Cod sursa (job #2287044) | Cod sursa (job #475946)
Cod sursa(job #475946)
//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;
}