Pagini recente » Cod sursa (job #1946164) | Cod sursa (job #2852738) | Cod sursa (job #2511892) | Cod sursa (job #3292805) | Cod sursa (job #1659176)
#include <algorithm>
#include <cstdio>
#include <cmath>
//#include <set>
using namespace std;
struct punct {
double x;
double y;
double unghi;
punct(const double &x = 0, const double &y = 0) {
this->x = x;
this->y = y;
}
punct operator += (const punct &arg) {
this->x += arg.x;
this->y += arg.y;
return *this;
}
punct operator -= (const punct &arg) {
this->x -= arg.x;
this->y -= arg.y;
return *this;
}
bool operator < (const punct &arg) const {
return this->unghi < arg.unghi;
}
};
const int NMAX = 120000;
const double EPS = 1e-8;
int N, M;
punct centru;
punct pct[1 + NMAX];
punct stiva[1 + NMAX];
//set <punct> st;
inline double cross_product(const punct &o, const punct &a, const punct &b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
void infas() {
sort(pct + 1, pct + 1 + N);
int num = 0;
for (int i = 1; i <= N; ++i) {
while (num >= 2 && cross_product(stiva[num - 1], stiva[num], pct[i]) <= EPS)
--num;
stiva[++num] = pct[i];
}
while (num > 2 && cross_product(stiva[num - 1], stiva[num], stiva[1]) <= EPS)
--num;
printf("%d\n", num);
for (int i = 1; i <= num; ++i)
printf("%f %f\n", stiva[i].x + centru.x, stiva[i].y + centru.y);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%lf%lf", &pct[i].x, &pct[i].y);
centru += pct[i];
}
centru.x /= N;
centru.y /= N;
for (int i = 1; i <= N; ++i) {
pct[i] -= centru;
pct[i].unghi = atan2(pct[i].y, pct[i].x);
}
infas();
return 0;
}