Pagini recente » Cod sursa (job #229338) | Cod sursa (job #3297322) | Cod sursa (job #1012033) | Cod sursa (job #2919611) | Cod sursa (job #1540148)
#include <fstream>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct du{
double x,y;}v[120111];
int i,n,curent,initial,start,poznoua,Re[120001],nr;
double Max;
bool viz[120001];
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
v[0].x=v[0].y=1000000000;
for(int i=1;i<=n;i++)
if (v[i].x<v[initial].x)
initial=i;
start=1;
curent=initial;
double last = 0;
while(start!=0||initial!=curent){
start=0;
Re[++nr]=curent;
Max=100000;
for(i=1;i<=n;i++){
if(i==curent||viz[i]==1)
continue;
double unghi = atan2((v[i].x -v[curent].x),v[i].y-v[curent].y);
if (unghi < 0) unghi += 2* M_PI;
unghi -= last;
if (unghi < 0) unghi += 2 * M_PI;
if (Max > unghi) {
Max= unghi;
poznoua = i;}
}
last = atan2(-(v[curent].x- v[poznoua].x),-(v[curent].y - v[poznoua].y));
if (last<0) last += 2 * M_PI;
curent = poznoua;
viz[curent] = 1;}
g<<nr<<'\n';
for(i=nr;i>=1;i--)
g<<v[Re[i]].x<<" "<<v[Re[i]].y<<'\n';;
return 0;
}