Pagini recente » Cod sursa (job #1580337) | Cod sursa (job #1892231)
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax = 120005;
struct Point{
double x,y;
}points[nmax];
int orientation(Point p, Point q, Point r){
double val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);
if(val==0)return 0;
return (val > 0)? 1 : 2;
}
void convexHull(Point points[], int n){
int i;
vector<Point>hull;
int l=0;
for(i=1;i<n;i++)
if(points[i].x<points[l].x)l=i;
int p=l,q;
do
{
hull.push_back(points[p]);
q=(p+1)%n;
for(i=0;i<n;i++)
if(orientation(points[p],points[i],points[q])==2)q=i;
p=q;
}while(p!=l);
g<<hull.size()<<'\n';
for(i=0;i<hull.size();i++)
g<<setprecision(12)<<hull[i].x<<" "<<hull[i].y<<'\n';
}
int main()
{
int n,i;
f >> n;
for(i=0;i<n;i++)
f>>points[i].x>>points[i].y;
g<<fixed;
convexHull(points,n);
return 0;
}