Pagini recente » Links | Rating Irimia Bogdan (IrimiaBogdan) | Cod sursa (job #776735) | Cod sursa (job #755464) | Cod sursa (job #418070)
Cod sursa(job #418070)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define EPS 0.000000000001
#define X first
#define Y second
typedef pair<double,double> dot;
int N, ind;
vector<dot> v;
vector<dot> stack;
dot p0;
bool cmp(dot a, dot b)
{
return (a.X - p0.X) * (b.Y - p0.Y) < (a.Y - p0.Y) * (b.X - p0.X);
}
double absf(double a) {
if ( a < 0 ) a *= -1;
return a;
}
double det(dot a, dot b, dot p) {
return (a.X - p.X) * (b.Y - p.Y) - (a.Y - p.Y) * (b.X - p.X);
}
int main()
{
ifstream f("infasuratoare.in");
ofstream f2("infasuratoare.out");
f >> N;
for ( int i = 0; i < N; ++i )
{
double dotX, dotY;
f >> dotX >> dotY;
v.push_back(make_pair(dotX,dotY));
}
p0 = v[0];
for ( int i = 0; i < N; ++i )
if ( v[i].X < p0.X || ( absf(v[i].X - p0.X) < EPS && v[i].Y < p0.Y ) )
{
p0 = v[i];
ind = i;
}
swap(v[v.size()-1], v[ind]);
sort(v.begin(), v.end() - 1, cmp);
stack.push_back(p0);
for ( int i = 0; i < v.size() - 1; ++i )
{
while ( stack.size() > 1 && det(v[i], stack[stack.size() - 2], stack[stack.size() - 1]) > 0 )
stack.pop_back();
stack.push_back(v[i]);
}
f2 << stack.size() << "\n";
for ( int i = 0; i < stack.size(); ++i )
f2 << stack[i].X << " " << stack[i].Y << endl;
return 0;
}