Pagini recente » Cod sursa (job #2352457) | Cod sursa (job #2587764) | Cod sursa (job #954758) | Cod sursa (job #696039) | Cod sursa (job #923568)
Cod sursa(job #923568)
#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{
int Aria = Arie(V[1], A, B);
if(fabs(Aria) < Eps) {
double tg = (A.y - B.y) / (A.x - B.x);
double An = A.y - tg * A.x;
double Bn = B.y - tg * B.x;
return An < Bn;
}
return Aria > 0 ;
}
};
void Read(){
fin >> N;
for(int i = 1; i <= N; ++i){
fin >> V[i].x >> V[i].y;
if(V[i].y < V[First].y || (fabs(V[i].y - V[First].y) <= Eps && V[First].x > V[i].x))
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(S[0] > 1 && Arie(V[S[S[0] - 1]], V[S[S[0]]], V[i]) < 0)
S[0]--;
S[++S[0]] = i;
}
fout << S[0]<<'\n';
fout << fixed << setprecision(6) << V[S[1]].x <<" " << V[S[1]].y <<'\n';
for(int i = 2; i <= S[0] ; ++i)
fout << fixed << setprecision(6) << V[S[i]].x <<" " << V[S[i]].y <<'\n';
}
int main(){
Read();
Inf();
return 0;
}