Pagini recente » Cod sursa (job #209585) | Cod sursa (job #684118) | Cod sursa (job #249457) | Cod sursa (job #2748208) | Cod sursa (job #2544021)
#include <bits/stdc++.h>
#define INF 1000000001
using namespace std;
int n, i, k;
bool ok;
struct dot
{
double x, y;
}v[120005], minn, sol[120005];
bool lefter(dot a, dot b, dot c)
{
double x1 = a.x - b.x;
double x2 = a.x - c.x;
double y1 = a.y - b.y;
double y2 = a.y - c.y;
double rez = y2 * x1 - y1 * x2;
if(rez > 0)return true;
return false;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> n;
minn.y = INF;
minn.x = INF;
for(i = 1; i <= n; i ++)
{
f >> v[i].x >> v[i].y;
if(v[i].y < minn.y)minn = v[i];
else if(v[i].y == minn.y && v[i].x < minn.x)minn = v[i];
}
sol[1] = minn;
k = 1;
do
{
ok = false;
for(i = 1; i <= n; i ++)
{
if(v[i].x == sol[k].x && v[i].y == sol[k].y)continue;
if(ok == false)
{
sol[ ++k] = v[i];
ok = true;
continue;
}
if(lefter(sol[k - 1], sol[k], v[i]))sol[k] = v[i];
}
}
while(sol[1].x != sol[k].x || sol[1].y != sol[k].y);
g << k - 1 << "\n";
for(i = k; i > 1; i --)
g << setprecision(12) << fixed << sol[i].x << " " << sol[i].y << "\n";
return 0;
}