Pagini recente » Cod sursa (job #357363) | Cod sursa (job #2515502) | Cod sursa (job #1646521) | Cod sursa (job #649291) | Cod sursa (job #2808791)
/*#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 1.2e5 + 1;
int n, punct_initial, cur, poznoua, ver[N];
double x[N], y[N], ma, unghi, last;
vector<int> ans;
bool misca = 1;
int main(){
f >> n;
for(int i = 1; i <= n; i++)
f >> x[i] >> y[i];
f.close();
x[0] = y[0] = 1e9;
for(int i = 1; i <= n; i++){
if(x[i] < x[punct_initial])
punct_initial = i;
}
cur = punct_initial;
while(misca || punct_initial != cur){
misca = 0; // doar la inceput si sfarsit vom trece prin punctul initial (nu il vom include a doua oara in vector)
ans.push_back(cur);
ma = 10000;
poznoua = cur; // poznoua = urm. punct
for(int i = 1; i <= n; i++){
if(ver[i] || i == cur) // nu ne intereseaza puncte deja vizitate (verificam si i == cur pentru prima iteratie)
continue;
unghi = atan2(x[i] - x[cur], y[i] - y[cur]); // facem diferenta pt. ca atan2 returneaza unghiul facut cu centrul => consideram centrul sa fie punctul curent
//cout << i << ' ' << cur << " ----- " << last / M_PI * 180 << " ";
if(unghi < 0)
unghi += 2 * M_PI;
//cout << unghi / M_PI * 180 << " ";
unghi -= last;
if(unghi < 0)
unghi += 2 * M_PI;
//cout << unghi / M_PI * 180 << '\n';
if(ma > unghi)
ma = unghi, poznoua = i;
}
last = atan2(x[poznoua] - x[cur], y[poznoua] - y[cur]);
if(last < 0)
last += 2 * M_PI;
cur = poznoua;
ver[cur] = 1;
}
reverse(ans.begin(), ans.end()); // vrem punctele in ordine trigonometrica
cout << ans.size() << '\n';
for(int i: ans)
cout << x[i] << ' ' << y[i] << '\n';
g.close();
}*/
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>
#define pb push_back
const int maxn = 120000;
using namespace std;
vector<int> VECT;
double X[maxn],Y[maxn];
int N,VER[maxn];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&N);
X[0] = 1000000000;Y[0] = 1000000000;
for(int i = 1;i <= N; ++i)
scanf("%lf %lf\n",&X[i],&Y[i]);
int punct_initial = 0;
int cur = 0;
int move = 1;
for(int i = 1;i <= N; ++i)
if (X[i] < X[punct_initial]) punct_initial = i;
cur = punct_initial;
double last = 0;
while(move || punct_initial != cur)
{
move = 0;
VECT.pb(cur);
double ma = 10000;
int poznoua = cur;
for(int i = 1;i <= N; ++i)
{
if (VER[i] || i == cur) continue;
double unghi = atan2((X[i] - X[cur]),Y[i] - Y[cur]);
if (unghi < 0) unghi += 2* M_PI;
unghi -= last;
if (unghi < 0) unghi += 2 * M_PI;
if (ma > unghi) {ma = unghi; poznoua = i;}
}
last = atan2(-(X[cur] - X[poznoua]),-(Y[cur] - Y[poznoua]));
if (last < 0) last += 2 * M_PI;
cur = poznoua;
VER[cur] = 1;
}
reverse(VECT.begin(),VECT.end());
printf("%d\n",VECT.size());
for(unsigned int i = 0;i < VECT.size(); ++i)
printf("%lf %lf\n",X[VECT[i]],Y[VECT[i]]);
return 0;
}