Pagini recente » Borderou de evaluare (job #1250002) | Monitorul de evaluare | Cod sursa (job #1885581)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define MAXN 120050
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct coord
{
double x, y;
bool operator<(const coord &e) const
{
if (x != e.x)
return x < e.x;
return y < e.y;
}
};
coord a[MAXN];
int n;
void read()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
}
double det(coord a, coord b, coord c)
{
return (c.y-a.y)*(b.x-a.x) - (c.x-a.x)*(b.y-a.y);
}
void add(vector<coord> &v, coord c)
{
while (v.size() >= 2 && det(v[v.size()-2], v.back(), c) < 0)
v.pop_back();
v.push_back(c);
}
vector<coord> cap, coada;
void solve()
{
sort(a+1, a+n+1);
for (int i = 1; i <= n; i++)
add(cap, a[i]);
for (int i = n-1; i >= 1; i--)
add(cap, a[i]);
cap.pop_back();
}
int main()
{
std::ios::sync_with_stdio(false);
read();
solve();
fout << cap.size() << "\n";
fout << setprecision(6) << fixed;
for (int i = 0, t = cap.size(); i < t; i++)
fout << cap[i].x << " " << cap[i].y << "\n";
return 0;
}