Pagini recente » Cod sursa (job #2684971) | Cod sursa (job #1382747) | Cod sursa (job #986961) | Cod sursa (job #3198355) | Cod sursa (job #2378938)
#include <bits/stdc++.h>
using namespace std;
struct punct
{
long double x, y;
}v[120005], sol[120005], val1, val2;
bool cmp(punct a, punct b)
{
return a.y < b.y;
}
int i, j, n, k;
bool ok, seen[120005];
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> n;
for(i = 1; i <= n; i ++)
f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
sol[++k] = v[1];
seen[1] = true;
do
{
for(i = 1; i <= n; i ++)
if(seen[i] == false)
{
ok = true;
val1.x = sol[k].x - v[i].x;
val1.y = sol[k].y - v[i].y;
for(j = 1; j <= n; j ++)
if(seen[j] == false && i != j)
{
val2.x = sol[k].x - v[j].x;
val2.y = sol[k].y - v[j].y;
if(val1.x * val2.y - val2.x * val1.y > 0)
{
ok = false;
break;
}
}
if(ok == true)
{
sol[++k] = v[i];
seen[i] = true;
break;
}
}
seen[1] = false;
}
while(sol[k].x != sol[1].x || sol[k].y != sol[1].y);
g << k - 1 << "\n";
reverse(sol + 1, sol + k + 1);
for(i = 1; i < k; i ++)
g << setprecision(12) << fixed << sol[i].x << " " << sol[i].y << "\n";
return 0;
}