Pagini recente » Cod sursa (job #2024374) | Cod sursa (job #1974733) | Cod sursa (job #485719) | Monitorul de evaluare | Cod sursa (job #967609)
Cod sursa(job #967609)
#include <iostream>
#include <iomanip>
#include <cmath>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#define F first
#define S second
using namespace std;
int main() {
int n;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin>>n;
vector< pair<double, double> > pist(n);
for(int i=0; i<n; ++i) fin>>pist[i].F>>pist[i].S;
sort(pist.begin(), pist.end());
vector< pair<double, double> > vastaus;
vastaus.push_back(pist[0]); //eniten vasemmalla
double pi=atan(1)*4;
int edel=0;
double ek=pi; //edellinen kulma
for(int i=0;;++i) {
if(vastaus[i]==vastaus[0] && i!=0) break;
double pienin=9999999; //pienin ero edelliseen
int pienink=0;//pienimmän koordinaatti
double pieninkulma=0;
for(int j=0; j<pist.size(); ++j) {
if(j==edel) {
continue;
}
double uk=0;
if(pist[j].F==pist[edel].F) {
if(pist[j].S>=pist[edel].S) {
uk=pi;
}
else uk=0;
goto ohi;
}
uk=atan((pist[j].S-pist[edel].S)/(pist[j].F-pist[edel].F));
if(pist[j].F<pist[edel].F) {
uk+=pi*1.5;
}
else uk+=pi/2;
ohi:;
//cout<<uk*180/pi<<' ';
double ero=0;
if(uk<=ek) {
ero=ek-uk;
}
else {
ero=2*pi-uk+ek;
}
if(ero<pienin) {
pienink=j;
pienin=ero;
pieninkulma=uk;
}
}
vastaus.push_back(pist[pienink]);
edel=pienink;
ek=pieninkulma;
}
fout<<vastaus.size()-1<<'\n';
fout<<fixed;
for(int i=vastaus.size()-2; i>=0; --i) {
fout<<setprecision(6)<<vastaus[i].F<<' '<<vastaus[i].S<<'\n';
}
}