Pagini recente » Cod sursa (job #1643185) | Cod sursa (job #3127244) | Cod sursa (job #2882788) | Cod sursa (job #1823674) | Cod sursa (job #902312)
Cod sursa(job #902312)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
//Definitii
#define point pair<double, double>
#define leftTurn(a,b,c) (det(a,b,c)>0)
//Constante
const int sz = (int)12e4+1;
//Functii
double det(point a, point b, point c)
{ return a.first*b.second + b.first*c.second + c.first*a.second - b.second*c.first - c.second*a.first - b.first*a.second; }
//Variabile
FILE *in,*out;
int num;
point points[sz];
point minPoint, current;
vector<point> convexeShell;
bool angle(point a, point b)
{ return leftTurn(minPoint,a,b); }
int main()
{
in=fopen("infasuratoare.in","rt");
out=fopen("infasuratoare.out","wt");
fscanf(in,"%d", &num);
fscanf(in,"%lf%lf",&minPoint.first,&minPoint.second);
for(int i=1; i<num; ++i)
{
fscanf(in,"%lf%lf",¤t.first,¤t.second);
if(current.second < minPoint.second || current.second == minPoint.second && current.first < minPoint.first)
{
points[i] = minPoint;
minPoint = current;
}
else points[i] = current;
}
//for(int i=1; i<=num; ++i)
// fprintf(out,"%lf %lf\n", points[i].first, points[i].second);
sort(points+1, points+num, angle);
convexeShell.reserve(num);
convexeShell.push_back(minPoint);
convexeShell.push_back(points[1]);
for(int i=2; i<num; ++i)
{
while(!leftTurn(convexeShell.at(convexeShell.size()-2), convexeShell.at(convexeShell.size()-1), points[i]))
convexeShell.pop_back();
convexeShell.push_back(points[i]);
}
fprintf(out,"%d\n",convexeShell.size());
vector<point>::iterator it, end = convexeShell.end();
for(it=convexeShell.begin(); it!=end; ++it)
fprintf(out,"%lf %lf\n", it->first, it->second);
fclose(in);
fclose(out);
return 0;
}