Pagini recente » Cod sursa (job #95333) | Cod sursa (job #1980666) | Cod sursa (job #3222663) | Cod sursa (job #3168649) | Cod sursa (job #2662260)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{
double x, y;
}puncte[120005];
int n;
bool viz[120005];
double miniY=0x3f3f3f3f, miniX=0x3f3f3f3f;
int indMini;
vector<int>rez;
int cautareInitiala()
{
for (int i=1; i<=n; ++i)
{
if (!viz[i])
return i;
}
}
double calcDet(punct a, punct b, punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
double calcDist(punct a, punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void solve()
{
bool gasit=false;;
int last=cautareInitiala();
while(true)
{
gasit=false;
for (int i=1; i<=n; ++i)
{
if (!viz[i]&& i!=last)
{
if (calcDet(puncte[rez[rez.size()-1]],puncte[last],puncte[i])>0)
last=i, gasit=true;
else if (calcDet(puncte[rez[rez.size()-1]],puncte[last],puncte[i])==0)
{
if (calcDist(puncte[rez[rez.size()-1]],puncte[last])>calcDist(puncte[rez[rez.size()-1]],puncte[i]))
{
last=i;
gasit=true;
}
}
}
}
if (!gasit)
return;
rez.push_back(last);
viz[last]=1;
last=rez[0];
}
}
int main()
{
f >> n;
for (int i=1; i<=n; ++i)
{
f >> puncte[i].x >> puncte[i].y;
if (puncte[i].x<miniX)
miniX=puncte[i].x, indMini=i, miniY=puncte[i].y;
else if (puncte[i].x==miniX && puncte[i].y<miniY)
miniY=puncte[i].y, indMini=i;
}
rez.push_back(indMini);
viz[indMini]=true;
solve();
for (auto &v:rez)
{
cout << puncte[v].x << ' ' << puncte[v].y << '\n';
}
return 0;
}