Pagini recente » Cod sursa (job #1564710) | Cod sursa (job #2828108) | Cod sursa (job #2059655) | Cod sursa (job #422102) | Cod sursa (job #1852305)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int Nmax = 1000;
int n;
struct Point
{
double x,y,id;
Point(): x(0),y(0),id(0) {}
};
Point p[Nmax+1];
int ST[Nmax+1];
inline double crossProduct(const Point &A,const Point &B,const Point &C) {
return 1LL * A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y);
}
inline bool comp(const Point &A,const Point &B) {
return crossProduct(p[1],A,B) < 0;
}
void solve()
{
for (int i = 2; i <= n; i++)
if ((p[i].x == p[1].x && p[i].y < p[1].y) || p[i].x < p[1].x)
swap(p[i],p[1]);
sort(p+2,p+n+1,comp);
ST[0] = 2; ST[1] = 1; ST[2] = 2;
for (int i = 3; i <= n; i++)
{
while (ST[0] >= 2 && crossProduct(p[ST[ST[0]-1]],p[ST[ST[0]]],p[i]) > 0)
ST[0]--;
ST[++ST[0]] = i;
}
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> p[i].x >> p[i].y;
p[i].id = i;
}
solve();
fout << ST[0] << "\n";
for (int i = 1; i <= ST[0]; i++)
fout << fixed << setprecision(7) << p[ST[i]].x << " " << p[ST[i]].y << "\n";
}