Pagini recente » Cod sursa (job #2263038) | Cod sursa (job #193172) | Cod sursa (job #708058) | Cod sursa (job #626296) | Cod sursa (job #1066264)
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define abs(x) ((x)>=0?(x):-(x))
#define ll long long
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Nmax = 120002;
const double prc = 1e-12;
int N;
bool equal(double a,double b){
return abs(a-b)<prc;
}
struct Point{
double x,y;
bool operator < (Point a){
if( equal(x,a.x) ) return y<a.y;
else return x<a.x;
}
} v[Nmax],S[Nmax]; int K;
double det(Point A,Point B,Point C){
return A.x*B.y - A.y*B.x + B.x*C.y - B.y*C.x + C.x*A.y - C.y*A.x;
}
bool cmp(Point a,Point b){
return det(v[1],a,b) < 0;
}
int main(){
in>>N;
for(int i=1;i<=N;i++){
in>>v[i].x>>v[i].y;
}
for(int i=1;i<=N;i++){
if(v[i]<v[1]) swap(v[i],v[1]);
}
sort(v+2,v+N+1,cmp);
S[++K]=v[1];
S[++K]=v[2];
for(int i=3;i<=N;i++){
while( K>=3 && det(S[K-1],S[K],v[i]) > 0 ) K--;
S[++K]=v[i];
}
out<<K<<'\n';
out.precision(9);out<<fixed;
for(int i=K;i>=1;i--) out<<S[i].x<<' '<<S[i].y<<'\n';
return 0;
}