Pagini recente » Cod sursa (job #399383) | Cod sursa (job #625571) | Cod sursa (job #316494) | Cod sursa (job #809404) | Cod sursa (job #1876939)
#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct point{
double X, Y;
};
int N;
point q;
double determ(point a, point b, point c){
return (b.X-a.X)*(c.Y-a.Y)-(b.Y-a.Y)*(c.X-a.X);
}
bool cmp(point a, point b){
return determ(q, a, b)>0;
}
int main(){
fstream f;
f.open("infasuratoare.in", ios_base::in);
f >> N;
vector<point> P(N);
for (int i=0; i<N; i++){
f >> P[i].X >> P[i].Y;
if (P[0].Y>P[i].Y || (P[0].Y==P[i].Y && P[0].X>P[i].X))
swap(P[i], P[0]);
}
f.close();
q=P[0];
sort(P.begin()+1, P.begin()+N, cmp);
vector<int> S;
S.push_back(0); S.push_back(1);
for (int i=2; i<N; i++){
while (S.size()>1 && determ(P[*(S.rbegin()+1)], P[S.back()], P[i])<=0)
S.pop_back();
S.push_back(i);
}
f.open("infasuratoare.out", ios_base::out);
f << fixed << S.size() << '\n';
for (unsigned int i=0; i<S.size(); i++)
f << setprecision(6) << P[S[i]].X << ' ' << P[S[i]].Y << '\n';
f.close();
return 0;
}