Pagini recente » Cod sursa (job #1582826) | Cod sursa (job #684509) | Cod sursa (job #955052) | Cod sursa (job #1816843) | Cod sursa (job #1529058)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x, y;
bool operator<(const point &p) const
{
return x < p.x || (x == p.x && y < p.y);
}
};
double dot(point o, point a, point b)
{
return (double) (a.x - o.x) * (b.y - o.y) - (double)(a.y - o.y)*(b.x-o.x);
}
vector <point> v, h;
int n;
point p;
int main()
{
int k = 0;
fin >> n;
for(int i = 0; i < n; i++)
{
fin >> p.x >> p.y;
v.push_back(p);
}
sort(v.begin(), v.end());
h.resize(2*n);
for(int i = 0; i < n; i++)
{
while(k >= 2 && dot(h[k-2], h[k-1], v[i]) <= 0) k--;
h[k++] = v[i];
}
for(int i = n-2, t = k+1; i >= 0; i--)
{
while( k >= t && dot(h[k-2], h[k-1], v[i]) <= 0) k--;
h[k++] = v[i];
}
h.resize(k);
fout << h.size()-1 << '\n';
for(int i = 0; i < h.size()-1; i++)
{
fout <<fixed << setprecision(6) << h[i].x << " " << h[i].y << '\n';
}
return 0;
}