Pagini recente » moisil_round_1 | Cod sursa (job #1382409) | Cod sursa (job #2904735) | Clasament 9i_beclean | Cod sursa (job #2659656)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
double x;
double y;
}puncte[120001];
int n;
vector<Punct>v1;
vector<Punct>v2;
bool cmp(Punct a, Punct b)
{
if(a.x == b.x)
{
if(a.y > a.x)
return 0;
return 1;
}
if(a.x < b.x)
return 1;
return 0;
}
void citire()
{
fin >> n;
for(int i = 0; i < n; i++)
fin >> puncte[i].x >> puncte[i].y;
sort(puncte, puncte + n, cmp);
}
double det(Punct a, Punct b, Punct c)
{
return a.x*b.y + b.x*c.y + a.y*c.x - a.x*c.y - c.x*b.y - b.x*a.y;
}
void rezolvare_prima_juma()
{
v1.push_back(puncte[0]);
v1.push_back(puncte[1]);
for(int i = 2; i < n; i++)
{
if(v1.size() == 1)
v1.push_back(puncte[i]);
else
{
while(v1.size() > 1 && det(v1[v1.size() - 2], v1[v1.size() - 1], puncte[i]) <= 0)
v1.pop_back();
v1.push_back(puncte[i]);
}
}
}
void rezolvare_a_doua_juma()
{
v2.push_back(puncte[n - 1]);
v2.push_back(puncte[n - 2]);
for(int i = n - 3; i >= 0; i--)
{
if(v2.size() == 1)
v2.push_back(puncte[i]);
else
{
while(v2.size() > 1 && det(v2[v2.size() - 2], v2[v2.size() - 1], puncte[i]) <= 0)
v2.pop_back();
v2.push_back(puncte[i]);
}
}
}
void afisare(vector<Punct> v, int start, int limita)
{
for(unsigned int i = start; i < v.size() - limita; i++)
{
fout << fixed << setprecision(6) << v[i].x << ' ';
fout << fixed << setprecision(6) << v[i].y << '\n';
}
}
int main()
{
citire();
rezolvare_prima_juma();
rezolvare_a_doua_juma();
fout << v1.size() + v2.size() - 2 << '\n';
afisare(v1, 0, 0);
afisare(v2, 1, 1);
return 0;
}