Pagini recente » Cod sursa (job #2989363) | Cod sursa (job #803146) | Cod sursa (job #377384) | Cod sursa (job #130241) | Cod sursa (job #3246667)
#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.y)
{
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 = 2, cnt = 0;
in >> n;
for(i = 1; i <= n; i++)
{
in >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmp);
s[1] = n;
s[2] = 1;
for(i = 2; i <= n - 1; i++)
{
if(arie(v[s[2]], v[s[1]], v[i]) < 0) /// jumatatea de sub dreapta
{
if(arie(v[s[s_size]], v[s[1]], v[i]) < 0)
{
bool ok = true;
while(s_size > 2 && ok == true)
{
if(arie(v[s[s_size - 1]], v[s[s_size]], v[i]) < 0)
{
s_size--;
}
else
{
ok = false;
}
}
s_size++;
s[s_size] = i;
}
}
}
int min_size = s_size;
s[s_size + 1] = 1;
s[s_size + 2] = n;
s_size += 2;
for(i = n - 1; i >= 2; i--)
{
if(arie(v[s[min_size + 1]], v[s[min_size + 2]], v[i]) > 0) /// jumatatea de deasupra dreaptei
{
if(arie(v[s[min_size + 1]], v[s[s_size]], v[i]) > 0)
{
cout << i << " ";
bool ok = true;
while(s_size > min_size + 2 && ok == true)
{
if(arie(v[s[s_size]], v[s[s_size - 1]], v[i]) > 0)
{
s_size--;
}
else
{
ok = false;
}
}
s_size++;
s[s_size] = i;
}
}
}
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;
}