Pagini recente » Cod sursa (job #1005235) | Cod sursa (job #658369) | Cod sursa (job #312906) | Cod sursa (job #1933635) | Cod sursa (job #965977)
Cod sursa(job #965977)
#include <iostream>
#include <cmath>
#include <utility>
#include <iomanip>
#include <bitset>
#include <fstream>
#define F first
#define S second
using namespace std;
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin>>n;
pair<double, double> p[120000];
for(int i=0; i<n; ++i) {
fin>>p[i].F>>p[i].S;
}
pair<double, double> v[120000];
bitset<120000> kay;
double pie=1e10;
int piek=0;
for(int i=0; i<n; ++i) {
if(pie>p[i].F) {
pie=p[i].F;
piek=i;
}
}
v[0].F=p[piek].F;
v[0].S=p[piek].S;
kay[piek]=1;
double pi = atan(1) * 4;
int k=1;
double ed=pi/2;
for(int i=0;;++i) { //cout<<v[i].F<<' '<<v[i].S<<'\n';
double upie=9999999999;
double ukul=0;
int loli=0;
pair<double, double> lol;
if(v[i]==v[0]&&i) break;
for(int j=0; j<n; ++j) {
// cout<<j<<'\n';
double ku=atan((p[j].S-v[i].S)/(p[j].F-v[i].F));
if(v[i]==p[j]) continue;
if(v[i].F==p[j].F) {
if(p[j].S>v[i].S) {
ku=pi/2;
}
else ku = pi*1.5;
}
else if(p[j].F<v[i].F) {
ku+=pi;
}
else if(p[j].S<v[i].S) {
ku+=pi*2;
}
ku = fmod(ku, 2*pi);
//cout<<(ku*180)/pi<<' '<<ed*180/pi<<' '<<abs(ku-ed)<<' '<<2*pi - max(ku, ed) + min(ku, ed)<<'\n';
if(ku>ed) {
double lol2=2*pi-ku + ed;
if(lol2<upie) {
upie=lol2;
ukul=ku;
lol=p[j];
loli=j;
}
}
else {
if(abs(ku-ed)<upie) {
upie=abs(ku-ed);
ukul=ku;
lol=p[j];
loli=j;
}
}
}
v[k]=lol;
ed=ukul;
kay[loli]=1;
++k;
}
fout<<k<<'\n';
fout<<fixed;
for(int i=k-1; i>=0; --i) {
fout<<setprecision(6)<<v[i].F<<' '<<v[i].S<<'\n';
}
fin.close();
fout.close();
}