Pagini recente » Cod sursa (job #1320809) | Cod sursa (job #1715255) | Cod sursa (job #1616818) | Cod sursa (job #733877) | Cod sursa (job #1608295)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream ka("infasuratoare.in");
ofstream ki("infasuratoare.out");
const int N_MAX = 120000;
int n;
struct Punct
{
double x, y;
bool operator < (const Punct arg) const
{
if(x == arg.x)
return y < arg.y;
else
return x < arg.x;
}
}puncte[N_MAX + 1], p_noi[N_MAX + 1];
stack <Punct> coada;
double cross_product(Punct a, Punct b, Punct c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int main()
{
ka >> n;
for(int i = 1; i <= n; i++)
ka >> puncte[i].x >> puncte[i].y;
sort(puncte + 1, puncte + n + 1);
coada.push(puncte[2]);
int curent = 2;
while(curent < n)
{
coada.push(puncte[++curent]);
Punct p1 = coada.top();
coada.pop();
Punct p2 = coada.top();
coada.pop();
while(!coada.empty() && cross_product(puncte[1], p1, p2) < 0)
{
p2 = coada.top();
coada.pop();
}
coada.push(p2);
coada.push(p1);
}
int primele = coada.size();
while(!coada.empty())
{
p_noi[coada.size() + 1] = coada.top();
coada.pop();
}
coada.push(puncte[2]);
curent = 2;
while(curent < n)
{
coada.push(puncte[++curent]);
Punct p1 = coada.top();
coada.pop();
Punct p2 = coada.top();
coada.pop();
while(!coada.empty() && cross_product(puncte[1], p1, p2) > 0)
{
p2 = coada.top();
coada.pop();
}
coada.push(p2);
coada.push(p1);
}
coada.pop();
primele++;
while(!coada.empty())
{
p_noi[++primele] = coada.top();
coada.pop();
}
p_noi[1] = puncte[1];
primele--;
ki << primele << '\n';
for(int i = primele; i >= 1; i--)
ki << fixed << setprecision(9) << p_noi[i].x << " " << p_noi[i].y << '\n';
}