Pagini recente » Clasamentul arhivei de probleme | Cod sursa (job #598105) | Cod sursa (job #2306198) | Cod sursa (job #2651429) | Cod sursa (job #582211)
Cod sursa(job #582211)
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>
#define pb push_back
const int MAX = 120000;
const int INF = 1000000000;
using namespace std;
vector<int> convexH;
double X[MAX], Y[MAX];
int N, viz[MAX];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int punct_initial = 0;
int crt = 0;
int move = 1;
double last = 0;
scanf("%d\n", &N);
X[0] = Y[0] = INF;
for(int i = 1; i <= N; ++i)
scanf("%lf %lf\n", &X[i], &Y[i]);
for(int i = 1; i <= N; ++i)
if (X[i] < X[punct_initial]) punct_initial = i;
crt = punct_initial;
while(move || punct_initial != crt)
{
move = 0;
convexH.pb(crt);
double ma = 10000;
int poznoua = crt;
for(int i = 1; i <= N; ++i)
{
if (viz[i] || i == crt) continue;
double unghi = atan2((X[i] - X[crt]), Y[i] - Y[crt]);
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[crt] - X[poznoua]), -(Y[crt] - Y[poznoua]));
if (last < 0) last += 2 * M_PI;
crt = poznoua;
viz[crt] = 1;
}
reverse(convexH.begin(), convexH.end());
printf("%d\n", convexH.size());
for(unsigned int i = 0; i < convexH.size(); ++i)
printf("%lf %lf\n", X[convexH[i]], Y[convexH[i]]);
return 0;
}