Pagini recente » Cod sursa (job #1135010) | Cod sursa (job #2157876) | Cod sursa (job #2413155) | Cod sursa (job #132713) | Cod sursa (job #2871138)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
const string filename = "infasuratoare";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
#define cx first
#define cy second
const int eps = 1e-6;
int n;
pair <double, double> pct[120005];
vector <int> sus, jos, ans;
double arie(int a, int b, int c)
{
/// ax ay 1
/// bx by 1 => ax * by + bx * cy + cx * ay - ax * cy - bx * ay - cx * by
/// cx cy 1
return pct[a].cx * pct[b].cy + pct[a].cy * pct[c].cx + pct[b].cx * pct[c].cy - pct[b].cy * pct[c].cx - pct[a].cy * pct[b].cx - pct[a].cx * pct[c].cy;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> pct[i].cx >> pct[i].cy;
sort(pct + 1, pct + n + 1);
sus.push_back(1);
jos.push_back(1);
for(int i = 2; i <= n; i++)
{
while(sus.size() > 1 && arie(sus[sus.size() - 2], sus[sus.size() - 1], i) > 0)
sus.pop_back();
sus.push_back(i);
while(jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1], i) < 0)
jos.pop_back();
jos.push_back(i);
}
fout << sus.size() + jos.size() - 2 << '\n';
for(int ind : jos)
ans.push_back(ind);
for(int i = sus.size() - 1; i >= 0; i--)
{
int ind = sus[i];
if(ind != 1 && ind != n)
ans.push_back(ind);
}
fout << setprecision(12) << fixed;
for(int ind : ans)
fout << pct[ind].cx << ' ' << pct[ind].cy << '\n';
return 0;
}