Pagini recente » Cod sursa (job #2238117) | Cod sursa (job #2143460) | Cod sursa (job #3166585) | Cod sursa (job #1982664) | Cod sursa (job #2241925)
#include <fstream>
#include <vector>
#include <algorithm> //sort
#include <iomanip> //setprecision
std::ifstream cin("infasuratoare.in");
std::ofstream cout("infasuratoare.out");
using namespace std;
#define maxn 130000
#define x first
#define y second
typedef pair <double,double> Point;
Point V[maxn],ans[maxn];
int N,head;
void citire(){
cin>>N;
for(int i=1;i<=N;i++){
cin>>V[i].x>>V[i].y;
}
}
double angle_Check(Point A,Point B,Point C){
return ((B.x-A.x)*(C.y-A.y))-((C.x-A.x)*(B.y-A.y));
}
bool cmp(Point A,Point B){
return angle_Check(V[1],A,B)<0;
}
void sort_v(){
head=1;
for(int i=2;i<=N;i++)
if(V[head]>V[i]) //compara first si dupa second in caz first==first
head=i;
swap(V[head],V[1]);
sort(V+2,V+N+1,cmp); //cmp e un criteriu de comparare in plus
}
void scan_Graham(){
sort_v();
ans[1]=V[1];
ans[2]=V[2];
for(int i=3;i<=N;i++){
while(head>=2&&angle_Check(ans[head-1],ans[head],V[i])>0)
head--;
ans[++head]=V[i];
}
}
int main()
{
citire();
scan_Graham();
cout<<fixed; //Couts the float no matter what, with a fixed
cout<<head-1<<'\n'; //number, in this case 9
for(int i=head;i>1;i--)
cout<<setprecision(9)<<ans[i].x<<' '<<ans[i].y<<'\n';
}