Pagini recente » Cod sursa (job #389774) | Cod sursa (job #2206287) | Cod sursa (job #2428323) | Cod sursa (job #273298) | Cod sursa (job #2985652)
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<fstream>
#include<iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point{
double x,y;
};
// Used to find the first node.
bool compare(const point&a, const point&b){
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
// Returns a number value between 0 and max.
int random(int max){
return rand()%max;
}
/* 1 1 1
* a.x b.x c.x
* a.y b.y c.y
*/
double determinant(const point&a, const point&b, const point&c){
return b.x*c.y + a.x*b.y + a.y*c.x - b.x*a.y - c.x*b.y - c.y*a.x;
}
int n;
vector<point> points;
void read(){
in>>n;
points.resize(n);
for(int i=0;i<n;i++){
in>>points[i].x>>points[i].y;
}
}
void solve(){
int first = 0;
for(int i=1;i<n;i++){
if(compare(points[i],points[first])){
first = i;
}
}
vector<point> hull;
bool stop = false;
int current = first;
while(!stop){
hull.push_back(points[current]);
int pivot;
do{
pivot = random(n);
}
while(pivot==current);
for(int i=0;i<n;i++){
if(determinant(points[current],points[pivot],points[i])<0.0){
pivot = i;
}
}
if(pivot == first){
stop = true;
}
current = pivot;
}
out<<hull.size()<<'\n';
for(point p:hull){
out<<fixed<<setprecision(10)<<p.x<<" "<<p.y<<'\n';
}
}
int main(){
read();
solve();
return 0;
}