Pagini recente » Istoria paginii utilizator/pestcontrol606 | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1539) | Cod sursa (job #531940)
Cod sursa(job #531940)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <math.h>
using namespace std;
double EPS = 1e-12;
struct point{
double x, y;
int index;
bool operator <(const point& other) const {
if (fabs(other.x-x) < EPS) return y < other.y;
else return x < other.x;
}
};
double double_area(point p1, point p2, point p3) {
// p1.x p1.y 1
// p2.x p2.y 1
// p3.x p3.y 1
double area = p2.x*p3.y - p2.y*p3.x
- (p1.x*p3.y - p1.y*p3.x)
+ (p1.x*p2.y - p1.y*p2.x);
return area;
}
vector<point> convex_hull(vector<point>& vec, int n) {
sort(vec.begin(), vec.end());
for (int i=0; i<n; i++) {
vec[i].index = i;
}
vector<point> rez;
bitset<120001> used; // 25KB
rez.push_back(vec[0]); used[0] = false; // add it as last element
rez.push_back(vec[1]); used[1] = true;
int siz = 2;
for (int i=2; i<n; i++) {
rez.push_back(vec[i]); siz++; used[i] = true;
while (siz > 2 && double_area(rez[siz-3], rez[siz-2], rez[siz-1]) <= 0) {
used[rez[siz-2].index] = false; rez[siz-2] = rez[siz-1]; siz--;
rez.pop_back();
}
}
for (int i=n-2; i>=0; i--) {
if (!used[i]) {
rez.push_back(vec[i]); siz++;
while (siz > 2 && double_area(rez[siz-3], rez[siz-2], rez[siz-1]) <= 0) {
rez[siz-2] = rez[siz-1]; siz--;
rez.pop_back();
}
}
}
// remove duplicate point
rez.pop_back();
return rez;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
scanf("%d", &n);
vector<point> vec(n);
for (int i=0; i<n; i++) {
scanf("%lf %lf", &vec[i].x, &vec[i].y);
}
vector<point> result = convex_hull(vec, n);
printf("%d\n", result.size());
for (int i=0; i<result.size(); i++) {
printf("%.6lf %.6lf\n", result[i].x, result[i].y);
}
return 0;
}