Pagini recente » Cod sursa (job #1750852) | Cod sursa (job #311248) | Cod sursa (job #1104885) | Cod sursa (job #210238) | Cod sursa (job #717668)
Cod sursa(job #717668)
/**
graham scan convex hull
**/
#include<stdio.h>
#include<assert.h>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
double minx, miny;
class point{
public:
double x, y;
point(){};
double dist(point other){
return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
}
friend bool operator < (point one, point other);
};
bool operator< (point one, point other){
double slope_other = (other.y - miny) / (other.x - minx);
double slope_here = (one.y - miny) / (one.x - minx);
if(slope_other == slope_here){
point aux;
aux.x = minx;
aux.y = miny;
return one.dist(aux) < other.dist(aux);
}
return !(slope_here < slope_other);
}
const int knmax = 120005;
const double keps = 0.000000001;
int points;
vector<int> index_stack;
point given[120005];
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;
}
bool must_decrease(){
if(index_stack.size() < 3)
return false; // we cannot remove any point from the stack
vector<int>::iterator it = index_stack.end() - 1;
return (ccw(given[*(it - 2)], given[*(it - 1)], given[*it]) > 0);
}
void solve(){
for(int i = 2; i <= points; ++i)
if(given[i].x < given[1].x)
swap(given[1], given[i]);
else if(given[i].y < given[1].y && given[i].x == given[1].x)
swap(given[1], given[i]);
minx = given[1].x;
miny = given[1].y;
// get certain point
sort(given + 2, given + points + 1);
// sort after slope, the < operator is overloaded
given[++points] = given[1];
// add first point at the end to ensure the corect hull
index_stack.push_back(1);
for(int i = 2; i <= points; ++i){
index_stack.push_back(i);
while(must_decrease()){
index_stack.pop_back();
index_stack.back() = i;
}
}
// we have the hull
index_stack.pop_back();
//remove the first element from the end of the stack
}
void write(){
assert(freopen("infasuratoare.out", "w", stdout) != NULL);
printf("%d\n", index_stack.size());
for(vector<int>::iterator it = index_stack.end() - 1; it >= index_stack.begin(); --it)
printf("%lf %lf\n", given[*it].x, given[*it].y);
//output the hull
}
int main(){
read();
solve();
write();
return 0;
}