Pagini recente » Cod sursa (job #3245127) | Cod sursa (job #297270) | Borderou de evaluare (job #2456784) | Cod sursa (job #1494234) | Cod sursa (job #717790)
Cod sursa(job #717790)
/**
lower hull and upper hull algorithm
**/
#include<stdio.h>
#include<assert.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
class point{
public :
double x, y;
point(){};
double dist(point other){
return sqrt((other.x - x) * (other.x - x) + (other.y - y) * (other.y - y));
}
friend bool operator < (point one, point other);
};
bool operator < (point one, point other){
return one.x < other.x;
}
const int knmax = 120005;
point given[knmax];
int points;
vector<int> index_up, index_down;
void read(){
assert(freopen("infasuratoare.in", "r", stdin) != NULL);
scanf("%d", &points);
for(int i = 1; i <= points; ++i)
scanf("%lf%lf", &given[i].x, &given[i].y);
}
double ccw(point one, point two, point three){
return ((two.y - three.y) * (one.x - two.x) - (two.x - three.x) * (one.y - two.y)) / 2;
}
int solve_stack(vector<int>::iterator it, double cof, int size){
int r_val = 0;
while(size >= 3 && (cof * ccw(given[*(it - 2)], given[*(it - 1)], given[*it])) >= 0){
--size;
++r_val;
*(it - 1) = *it;
--it;
}
return r_val;
}
void solve(){
sort(given + 1, given + points + 1);
// get the start and the end
index_up.push_back(1);
index_down.push_back(1);
// the start point
int j;
for(int i = 2; i <= points; ++i){
double aux = ccw(given[1], given[points], given[i]);
if(aux <= 0){
index_up.push_back(i);
j = solve_stack(index_up.end() - 1, -1.0, index_up.size());
while(j){
--j;
index_up.pop_back();
}
}
if(aux >= 0){
index_down.push_back(i);
j = solve_stack(index_down.end() - 1, 1.0, index_down.size());
while(j){
--j;
index_down.pop_back();
}
}
}
// the hull algorithm, notice it is a lot easier to code than the graham scan
// because the complexity of the algorithms is given by the sorting of the points
// this one is faster because we have a smaller constant in sorting
}
void write(){
assert(freopen("infasuratoare.out", "w", stdout) != NULL);
printf("%d\n", index_up.size() + index_down.size() - 2);
//number of points in the hull, decreasing 2 because end and start are counted twice
for(vector<int>::iterator it = index_up.begin(); it < index_up.end(); ++it)
printf("%lf %lf\n", given[*it].x, given[*it].y);
for(vector<int>::iterator it = index_down.end() - 2; it > index_down.begin(); --it)
printf("%lf %lf\n", given[*it].x, given[*it].y);
}
int main(){
read();
solve();
write();
return 0;
}