Pagini recente » Cod sursa (job #3202819) | Cod sursa (job #3212215) | Rating Banu Matei Costin (mateibanu) | Cod sursa (job #1198873) | Cod sursa (job #3299520)
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define MAX_POINTS 120005
typedef struct {
double x, y;
} Point;
Point p[MAX_POINTS];
bool cmp(Point a, Point b) {
if (a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
int det_sign(Point a, Point b, Point c) {
double det = a.x * b.y - b.y * c.x + b.x * c.y - c.y * a.x + c.x * a.y - a.y * b.x;
if (det > 0) return 1;
if (det < 0) return -1;
return 0;
}
int ans[MAX_POINTS];
int main() {
int n;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1, cmp);
ans[++ans[0]] = 1;
ans[++ans[0]] = 2;
for (int i = 3; i <= n; i++) {
int sz = ans[0];
while (sz > 1 && det_sign(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1)
{
ans[0]--;
sz = ans[0];
}
ans[++ans[0]] = i;
}
for (int i = n - 1; i >= 1; i--) {
int sz = ans[0];
while (sz > 1 && det_sign(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1) {
ans[0]--;
sz = ans[0];
}
ans[++ans[0]] = i;
}
fout << ans[0] - 1 << '\n';
for (int i = 1; i < ans[0]; i++) {
fout << fixed << setprecision(12) << p[ans[i]].x << " " << p[ans[i]].y << '\n';
}
fout.close();
return 0;
}