Pagini recente » Cod sursa (job #1694251) | Cod sursa (job #652325) | Cod sursa (job #901830) | Cod sursa (job #982712) | Cod sursa (job #682707)
Cod sursa(job #682707)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct punct
{
float x, y;
punct(){x=y=0;}
punct(float X, float Y) { x = X; y = Y; }
};
vector<punct> puncte, sol;
punct init;
bool sortfunc(punct a, punct b)
{
return (a.x - init.x) * (b.y - init.y) > (b.x - init.x) * (a.y - init.y);
}
bool right(punct a, punct b, punct c)
{
return (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - c.x * b.y - a.x * c.y) > 0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i, n, j = 0;
float x, y;
scanf("%d",&n);
puncte.resize(n);
for(i = 0;i < n;i++)
{
scanf("%f %f", &x, &y);
puncte[i] = punct(x, y);
if(x < puncte[j].x or (x == puncte[j].x and y < puncte[j].y))
j = i;
}
init = puncte[j];
puncte.erase(puncte.begin() + j);
sort(puncte.begin(), puncte.end(), sortfunc);
sol.push_back(init);
for(i = 0;i < puncte.size();i++)
{
while(sol.size() > 1 and !right(*(sol.end() - 2), *(sol.end() - 1), puncte[i]))
sol.pop_back();
sol.push_back(puncte[i]);
}
printf("%d\n", sol.size());
for(i = 0;i < (signed)sol.size();i++)
printf("%f %f\n", sol[i].x, sol[i].y);
return 0;
}