Pagini recente » Cod sursa (job #2123194) | Cod sursa (job #1450659) | Cod sursa (job #1499350) | Cod sursa (job #1216335) | Cod sursa (job #876422)
Cod sursa(job #876422)
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>
#define max_n 120000
using namespace std;
vector <int> v;
vector <int>::iterator it;
double x[max_n],y[max_n];
double u,z,unghi;
int i,in,n,c,poz,h;
bool ok,use[max_n];
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for (i=1; i<=n; i++)
scanf("%lf%lf",&x[i],&y[i]);
in=1; // indicele punctului de plecare
for (i=2; i<=n; i++)
if (x[i]<x[in]) in=i; //alegem cel mai de jos punct
c=in; // c=indicele punctului curent
u=0;
ok=true;
while (ok || in!=c){
ok=false;
printf("1");
v.push_back(c); //se retine in v(vectorul punctelor de pe infasuratoare) elementul curent
poz=c;
z=10000;
for (i=1; i<=n; i++) /* se gaseste cel mai mare unghi facut de dreapta suport cu unul dintre punctele neselectate pe infasuratoare
S-a utilizat functia predefinita "atan2"(arctg(y/x), in intervalul [-pi,+pi] rad ) */{
if (use[i] || i==c) continue; //se pot utiliza doar punctele neaflate inca pe infasuratoare
unghi=atan2((x[i]-x[c]),(y[i]-y[c]));
if (unghi<0)
unghi+=2 * M_PI;
unghi-=u;
if (unghi<0)
unghi+=2 * M_PI;
if (z>unghi) {
z=unghi;
poz=i;
}
}
u=atan2(-(x[c]-x[poz]),-(y[c]-y[poz]));
if (u<0)
u+=2 * M_PI;
c=poz; // se actualizeaza pozitia curenta
use[c]=true; //se valideaza utilizarea punctului curent
}
reverse(v.begin(),v.end()); //pentru ordine trigonometrica
h=v.size(); //nr de puncte de pe infasuratoare
printf("%d\n",h);
for (i=0; i<h; i++)
printf("%lf %lf\n",x[v[i]],y[v[i]]);
return 0;
}