Pagini recente » Cod sursa (job #2052321) | Cod sursa (job #1746986) | Cod sursa (job #50566) | Cod sursa (job #688258) | Cod sursa (job #901059)
Cod sursa(job #901059)
#include<fstream>
#include<stack>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax = 120009;
const double Eps = 0.00001;
struct Point{ double x, y;}V[Nmax];
int S[Nmax]; int First = 1; int N;
double Arie(const Point V1,const Point V2,const Point V3){
return V1.x * V2.y + V2.x * V3.y + V3.x * V1.y - V1.y * V2.x - V2.y * V3.x - V3.y * V1.x;
}
struct cmp{
bool operator ()(const Point &A,const Point &B)const{
return Arie(V[1], A, B) <0 ;
}
};
void Read(){
fin >> N;
for(int i = 1; i <= N; ++i){
fin >> V[i].x >> V[i].y;
if(V[i].x < V[First].x || (fabs(V[i].x - V[First].x) < Eps && V[First].y > V[i].y))
First = i;
}
swap(V[1], V[First]);
sort(V + 2, V + 1 + N, cmp());
}
void Inf(){
S[0] = 2; S[1] = 1;S[2] = 2;
for(int i = 3; i <= N; ++i){
while(Arie(V[S[S[0] - 1]], V[S[S[0]]], V[i]) > 0 && S[0] >= 2) S[0]--;
S[++S[0]] = i;
}
fout << S[0]<<'\n';
for(int i = S[0] ; i ; --i)
fout << fixed<<setprecision(6) << V[S[i]].x <<" "<<V[S[i]].y <<'\n';
}
int main(){
Read();
Inf();
return 0;
}