Pagini recente » Cod sursa (job #1839803) | Cod sursa (job #2167958) | Cod sursa (job #828556) | Cod sursa (job #966406)
Cod sursa(job #966406)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
#define inf 1000000000
typedef struct
{
double x, y;
} Point;
vector<Point>points;
vector<Point> stive;
int N;
Point p;
double cross_prod(Point A, Point B, Point C )
{
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
bool comp(Point A, Point B)
{
if(cross_prod(points[0], A, B) < 0)
return false;
else
return true;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> N;
//read from file
for(int i=1; i<=N; i++)
{
f >> p.x >> p.y;
points.push_back(p);
}
//find minimum
Point min;
min.x=inf;
min.y=inf;
for(size_t i=0; i<points.size(); i++)
{
if(points[i].y < min.y)
{
min.y = points[i].y;
min.x = points[i].x;
}
else if(points[i].y == min.y)
{
if(points[i].x < min.x)
{
min.y = points[i].y;
min.x = points[i].x;
}
}
else
continue;
}
//make minimum first element for graham scan
swap(min,points[0]);
//sort elements acording to the polar angle with respect to first point
vector<Point>::iterator it = points.begin();
++it;
sort(it, points.end(), comp);
stive.push_back(points[0]);
stive.push_back(points[1]);
stive.push_back(points[2]);
//grahams scan
for(size_t i=3; i<points.size(); i++)
{
while(cross_prod(stive[stive.size()-2], stive[stive.size()-1],points[i]) < 0)
{
stive.pop_back();
}
stive.push_back(points[i]);
}
g<<fixed<<stive.size()<<endl;
for(size_t i=0; i<stive.size(); i++)
{
g<<setprecision(9);
g<<stive[i].x <<" "<<stive[i].y<<endl;
}
return 0;
}