Pagini recente » Cod sursa (job #2115872) | Cod sursa (job #406219) | Cod sursa (job #264896) | Cod sursa (job #3004847) | Cod sursa (job #800478)
Cod sursa(job #800478)
// 3 puncte (x1, y1), (x2, y2), (x3, y3)
// Daca (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) == 0, punctele sunt coliniare
// Daca > 0, drumul va "vira" la stanga
// Daca < 0, drumul va "vira" la dreapta
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 120005;
const double INF = 1000000005;
const double MIN = 0.00001;
struct infasuratoare{
double x, y;
};
int n, nr;
vector<pair<double, double> > v;
infasuratoare stack[N];
int compare(double a, double b) {
if (a - b > MIN)
return 1;
if (b - a > MIN)
return -1;
return 0;
}
bool comp(pair<double, double> a, pair<double, double> b) {
if (compare( (v[0].second - a.second) * (v[0].first - b.first), (v[0].first - a.first) * (v[0].second - b.second) ) == - 1)
return true;
return false;
}
void read() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
double x, y;
scanf("%lf %lf", &x, &y);
v.push_back(make_pair(x, y));
}
}
void set_points() {
double ymin = INF;
int pos;
for (int i = 0; i < n; ++i)
if (v[i].second < ymin) {
ymin = v[i].second;
pos = i;
}
swap(v[pos].first, v[0].first);
swap(v[pos].second, v[0].second);
sort(v.begin() + 1, v.end(), comp);
}
inline int turn(infasuratoare p1, infasuratoare p2, pair<double, double> p3) {
return (p2.x - p1.x) * (p3.second - p1.y) - (p2.y - p1.y) * (p3.first - p1.x);
}
void solve() {
nr = 1;
stack[0].x = v[0].first;
stack[0].y = v[0].second;
stack[1].x = v[1].first;
stack[1].y = v[1].second;
for (int i = 2; i < n; ++i) {
int res = turn(stack[nr - 1], stack[nr], v[i]);
if (res >= 0) {
stack[++nr].x = v[i].first;
stack[nr].y = v[i].second;
continue;
}
if (res < 0) {
--nr;
--i;
continue;
}
}
}
void write() {
printf("%d\n", nr + 1);
for (int i = 0; i <= nr; ++i)
printf("%lf %lf\n", stack[i].x, stack[i].y);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
set_points();
solve();
write();
return 0;
}