Pagini recente » Cod sursa (job #2760438) | Cod sursa (job #799726) | Cod sursa (job #1229998) | Cod sursa (job #3182550) | Cod sursa (job #3221828)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double eps = 1.0e-12;
struct POINT{
double x, y;
};
POINT P[120005];
POINT LL;
int h[120005];
double cp(POINT A, POINT B, POINT C){
return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}
int ccw(POINT A, POINT B, POINT C){
double cpp = cp(A, B, C);
if(fabs(cpp) < eps)
return 0;
if(cpp >= eps)
return 1;
return -1;
}
bool cmp(POINT P1, POINT P2){
return ccw(LL, P1, P2) >= 0;
}
int main()
{
int n, i, top;
double tx, ty;
fin >> n;
//LL sa contina punctul y minim si cu x minim
fin >> tx >> ty;
LL.x = tx;
LL.y = ty;
P[0] = LL;
for(i = 1; i < n; ++i){
fin >> tx >> ty;
P[i].x = tx;
P[i].y = ty;
if(ty - LL.y <= -eps || (fabs(LL.y - ty) < eps && tx - LL.x <= -eps)){
LL.x = tx;
LL.y = ty;
P[i] = P[0];
P[0] = LL;
}
}
sort(P + 1, P + n, cmp);
P[n] = LL; //inchidere linie franta
h[0] = 0;
h[1] = 1;
top = 1;
i = 2;
while(i <= n){
if(ccw(P[h[top - 1]], P[h[top]], P[i]) > 0){
h[++top] = i;
i++;
}
else
top--;
}
fout << top << "\n";
fout << showpoint << fixed << setprecision(6);
for(i = 0; i < top; ++i)
fout << P[h[i]].x << " " << P[h[i]].y << "\n";
fin.close();
fout.close();
return 0;
}