Pagini recente » Cod sursa (job #27444) | Cod sursa (job #2826462) | Cod sursa (job #2915853) | Cod sursa (job #1782758) | Cod sursa (job #3246676)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct ura
{
double x, y;
} v[120001];
int s[120001];
bool cmp(ura a, ura b)
{
/// a < b == 1
if(a.x < b.x)
{
return true;
}
else if(a.x > b.x)
{
return false;
}
else
{
if(a.y < b.y)
{
return true;
}
else
{
return false;
}
}
}
long long arie(ura a, ura b, ura c)
{
return (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x);
}
int main()
{
int n, i, s_size = 1, cnt = 0, mic, mare;
in >> n;
for(i = 1; i <= n; i++)
{
in >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmp);
mic = 1;
mare = n;
s[1] = 1;
for(i = 2; i <= n - 1; i++)
{
if(arie(v[mic], v[mare], v[i]) < 0) /// sub dreapta
{
if(arie(v[s[s_size]], v[mare], v[i]) < 0)
{
while(s_size > 1 && arie(v[s[s_size - 1]], v[s[s_size]], v[i]) < 0)
{
s_size--;
}
s[++s_size] = i;
}
}
}
for(i = 1; i <= s_size; i++)
{
// cout << s[i] << " ";
}
s[++s_size] = n;
int min_size = s_size;
for(i = n - 1; i >= 1; i--)
{
if(arie(v[mic], v[mare], v[i]) > 0) /// deasupra dreptei
{
if(arie(v[mic], v[s[s_size]], v[i]) > 0)
{
while(s_size > min_size && arie(v[s[s_size]], v[s[s_size - 1]], v[i]) > 0)
{
s_size--;
}
s[++s_size] = i;
}
}
}
s[++s_size] = 1;
out << s_size - 1 << "\n";
for(i = 2; i <= s_size; i++)
{
out << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
}
// out << s_size - 2 << "\n";
// for(i = 3; i <= min_size; i++)
// {
// out << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
// }
// out << fixed << setprecision(6) << v[s[min_size + 2]].x << " " << v[s[min_size + 2]].y << "\n"; /// cel mai din dr
// for(i = min_size + 3; i <= s_size; i++)
// {
// out << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
// }
// out << fixed << setprecision(6) << v[s[min_size + 1]].x << " " << v[s[min_size + 1]].y << "\n"; /// cel mai din st
return 0;
}