Pagini recente » Cod sursa (job #478779) | Cod sursa (job #731758) | Cod sursa (job #2729120) | Cod sursa (job #2707018) | Cod sursa (job #904167)
Cod sursa(job #904167)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define MAX 130000
using namespace std;
typedef struct
{
double x, y;
} point;
point P[MAX];
int n, i, st, Max, S[MAX];
double X, Y;
bool out(int i1, int i2, int i3)
{
return P[i1].x*P[i2].y + P[i2].x*P[i3].y + P[i3].x*P[i1].y - P[i3].x*P[i2].y - P[i1].x*P[i3].y - P[i2].x*P[i1].y > 0;
}
bool cmp(point i, point j)
{
return (i.y - Y) * (j.x - X) < (j.y - Y) * (i.x - X);
}
int main()
{
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
fi >> n;
P[0].x = P[0].y = int(2e9);
for(i = 1; i <= n; i++)
{
fi >> P[i].x >> P[i].y;
if(P[i].x < P[Max].x or (P[i].x == P[Max].x and P[i].y < P[Max].y))
Max = i;
}
X = P[Max].x; Y = P[Max].y;
swap(P[1], P[Max]);
sort(P+2, P+n+1, cmp);
P[++n] = P[1];
S[++st] = 1;
for(i = 2; i <= n; i++)
{
while(st > 1 and out(S[st], S[st-1], i)) st--;
S[++st] = i;
}
fo << setprecision(6) << fixed;
fo << st-1 << "\n";
for(i = 1; i < st; i++) fo << P[S[i]].x << " " << P[S[i]].y << "\n";
return 0;
}