Pagini recente » Cod sursa (job #2632190) | Cod sursa (job #925065) | Cod sursa (job #1505766) | Cod sursa (job #1123422) | Cod sursa (job #2697805)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct
{
double x, y;
};
Punct P[120002], St[120002];
int N, H;
void afis()
{
g << H << '\n';
g << fixed << setprecision(6);
for(int i = 1; i <= H; i++)
g << St[i].x << ' ' << St[i].y << '\n';
}
void swap(Punct &A, Punct &B)
{
Punct aux = A;
A = B;
B = aux;
}
inline double patrat(double x)
{
return x * x;
}
double distp(const Punct &A, const Punct &B)
{
return patrat(A.x - B.x) + patrat(A.y - B.y);
}
bool compy(const Punct &A, const Punct &B)
{
if(A.y == B.y)
return A.x < B.x;
return A.y < B.y;
}
double det(const Punct &A, const Punct &B, const Punct &C)
{
return (A.x - B.x) * (B.y - C.y) - (A.y - B.y) * (B.x - C.x);
}
bool compd(const Punct &A, const Punct &B)
{
double dd = det(P[1], A, B);
if(dd == 0)
return distp(P[1], A) < distp(P[1], B);
return dd > 0;
}
int main()
{
f >> N;
int pmin = 1;
for(int i = 1; i <= N; i++)
{
f >> P[i].x >> P[i].y;
if(compy(P[i], P[pmin]))
pmin = i;
}
swap(P[pmin], P[1]);
sort(P + 2, P + N + 1, compd);
St[1] = P[1];
St[2] = P[2];
H = 2;
P[N + 1] = P[1];
for(int i = 3; i <= N + 1; i++)
{
while(H >= 2 && det(St[H - 1], St[H], P[i]) < 0)
H--;
St[++H] = P[i];
}
H--;
afis();
return 0;
}