Pagini recente » Cod sursa (job #562075) | Cod sursa (job #992411) | Cod sursa (job #1820774) | Cod sursa (job #2165706) | Cod sursa (job #475962)
Cod sursa(job #475962)
//qhull
/**
*1) se cel mai din stanga punct(A) si cel mai din dreapta(B)
*2) se cauta cel mai departat punct P fata de AB(din stanga si din dreapta).Acesta va apartine sigur infasuratorii
*3) se sterg toate punctele din interiorul triunghiului PAB
*4) se cauta iarasi cel mai departat punct si repetam pasii
*/
#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) {//stanga sau dreapta lui ab
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,dpunct2;
for(i=set.begin(); i!=set.end(); ++i) {
int distanta=distance((*a),(*b),(*i));
if(distanta>dist) {//cel mai departat punct
dist=distanta;
dpunct=i;
}
}
punct p=(*dpunct);
dpunct2=convexHull.insert(b,p);//il adaugam
set.erase(dpunct);
list<punct> leftSetAP,leftSetPB;//punctele din dreapta si din stanga
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,dpunct2,leftSetAP);
hullSet(dpunct2,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) {//gasim punctul cel mai din stanga si cel mai din dreapta
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) {//gasim punctele din stanga si din dreapta
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;
}