Pagini recente » Cod sursa (job #2436429) | Cod sursa (job #1949950) | Cod sursa (job #140548) | Cod sursa (job #1684980) | Cod sursa (job #1608340)
#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[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();
Punct p3 = coada.top();
coada.pop();
while(!coada.empty() && cross_product(p3, p2, p1) <= 0)
{
p2 = p3;
p3 = coada.top();
coada.pop();
}
coada.push(p3);
if(cross_product(p3, p2, p1) > 0)
coada.push(p2);
coada.push(p1);
}
int primele = coada.size();
while(!coada.empty())
{
p_noi[coada.size()] = coada.top();
coada.pop();
}
coada.push(puncte[1]);
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();
Punct p3 = coada.top();
coada.pop();
while(!coada.empty() && cross_product(p3, p2, p1) >= 0)
{
p2 = p3;
p3 = coada.top();
coada.pop();
}
coada.push(p3);
if(cross_product(p3, p2, p1) < 0)
coada.push(p2);
coada.push(p1);
}
coada.pop();
while(!coada.empty())
{
p_noi[++primele] = coada.top();
coada.pop();
}
primele--;
ki << primele << '\n';
for(int i = 1; i <= primele; i++)
ki << fixed << setprecision(9) << p_noi[i].x << " " << p_noi[i].y << '\n';
}