Pagini recente » Cod sursa (job #1194931) | Cod sursa (job #2369580) | Cod sursa (job #283848) | Cod sursa (job #2205009) | Cod sursa (job #2916482)
/// Preset de infoarena
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int maxN = 120005;
int n, k;
struct point {
double x, y;
bool operator < (const point &other) const {
if(x == other.x)
return y < other.y;
return x < other.x;
}
}pct[maxN], v[maxN];
double arie(point a, point b, point c)
{
/// ax ay 1 )
/// bx by 1 ) => A = ax * by + bx * cy + cx * ay - ax * cy - bx * ay - cx * by
/// cx cy 1 )
return a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - a.y * b.x - a.x * c.y;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> pct[i].x >> pct[i].y;
sort(pct + 1, pct + n + 1);
vector <point> sus, jos;
sus.push_back(pct[1]);
jos.push_back(pct[1]);
for(int i = 2; i <= n; i++)
{
while(sus.size() > 1 && arie(sus[sus.size() - 2], sus[sus.size() - 1], pct[i]) >= 0)
sus.pop_back();
sus.push_back(pct[i]);
while(jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1], pct[i]) <= 0)
jos.pop_back();
jos.push_back(pct[i]);
}
sus.pop_back();
reverse(sus.begin(), sus.end());
sus.pop_back();
for(auto elem : jos)
v[++k] = elem;
for(auto elem : sus)
v[++k] = elem;
fout << k << '\n';
fout << setprecision(12) << fixed;
for(int i = 1; i <= k; i++)
fout << v[i].x << ' ' << v[i].y << '\n';
return 0;
}