Pagini recente » Cod sursa (job #2505693) | Cod sursa (job #3338636) | Cod sursa (job #468498) | Cod sursa (job #3344415) | Cod sursa (job #3332716)
#include <bits/stdc++.h>
using namespace std;
#define DIM 10000
char buff[DIM];
int poz=0;
void citeste(double &numar)
{
numar = 0;
char semn='+';
//caut inceputul numarului
while (buff[poz] < '0' || buff[poz] > '9')
{
semn = buff[poz];
if (++poz == DIM)
fread(buff,1,DIM,stdin),poz=0;
}
//citesc partea de dinainte de virgula
while ('0'<=buff[poz] && buff[poz]<='9')
{
numar = numar*10 + buff[poz] - '0';
if (++poz == DIM)
fread(buff,1,DIM,stdin),poz=0;
}
//daca are virgula citesc si partea de dupa
if (buff[poz] == '.')
{
double tmp,cnt;
tmp = 0;
cnt = 1;
++poz;
while ('0'<=buff[poz] && buff[poz]<='9')
{
cnt = cnt/10;
tmp = tmp + cnt*(double(buff[poz]-'0'));
if (++poz == DIM)
fread(buff,1,DIM,stdin),poz=0;
}
numar += tmp;
}
//daca are semnul minus il fac negativ
if (semn == '-')
numar = - numar;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main() {
int n, verif[120001] = {0};
double x[120001], y[120001];
vector<int> v;
ios::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
//freopen("infasuratoare.in","r",stdin);
//freopen("infasuratoare.out","w",stdout);
//scanf("%d\n",&n);
fin >> n;
x[0] = 1000000000; y[0] = 1000000000;
int initial = 0;
for (int i = 1; i <= n; i++)
{
//fin >> x[i];
//fin>> y[i];
citeste(x[i]);
citeste(y[i]);
//scanf("%lf %lf\n",&x[i],&y[i]);
if (x[i] < x[initial]) initial = i;
}
int acuma = initial;
double inainte = 0;
do
{
v.push_back(acuma);
double maxim = DBL_MAX;
int nou = acuma;
for (int i = 1; i <= n; i++)
{
if (acuma != i && !verif[i])
{
double unghi = atan2((x[i] - x[acuma]), (y[i] - y[acuma]));
if (unghi < 0) unghi += 2 * M_PI;
unghi = unghi - inainte;
if (unghi < 0) unghi += 2 * M_PI;
if (unghi < maxim)
{
maxim = unghi;
nou = i;
}
}
}
inainte = atan2(x[nou] - x[acuma], y[nou] - y[acuma]);
if (inainte < 0) inainte += 2 * M_PI;
acuma = nou;
verif[nou] = 1;
} while (initial != acuma);
reverse(v.begin(), v.end());
fout << v.size() << '\n';
fout << setprecision(12) << fixed;
//printf("%d\n",v.size());
for (auto i : v)
{
//printf("%lf %lf\n",x[i],y[i]);
fout << x[i] << " " << y[i] << '\n';
}
return 0;
}