Pagini recente » Cod sursa (job #1149317) | Cod sursa (job #3146344) | Cod sursa (job #1409449) | Cod sursa (job #1477777) | Cod sursa (job #1509846)
#include <bits/stdc++.h>
#define eps 1e-12
/// eps este 10^(-12) , se foloseste pentru diferente foarte mici , de exemplu 1.00000006 si 1.00000003
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax=120005;
struct punct {double x,y;};
punct a[nmax];
punct stiv1[nmax];
punct stiv2[nmax];
int n,i,stiv1_size,stiv2_size;
bool cmpy (punct A , punct B)
{
if (A.x!=B.x) return A.x<B.x;
return A.y<B.y;
}
double cross_product (punct O,punct A,punct B) /// O este punctul noua origine
{
A.x-=O.x;
A.y-=O.y;
B.x-=O.x;
B.y-=O.y;
return A.x*B.y-A.y*B.x;
}
int main()
{
f>>n;
for (i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmpy);
stiv1_size=2;
stiv1[1]=a[1];
stiv1[2]=a[2];
for (i=3;i<=n;i++) /// partea de jos (pentru ca le-am ordonat dupa x , vom veni din stnanga jos)
{
while (stiv1_size>=2 && cross_product(stiv1[stiv1_size-1],stiv1[stiv1_size],a[i])<eps) /// cand cross-productul este mai mic decat 0 (sau epsilon) , inseamna ca punctul actual scoate punctul de dinainte
stiv1_size--;
stiv1[++stiv1_size]=a[i];
}
stiv2_size=2;
stiv2[1]=a[n];
stiv2[2]=a[n-1];
for (i=n-2;i>=1;i--) /// partea de sus
{
while (stiv2_size>=2 && cross_product(stiv2[stiv2_size-1],stiv2[stiv2_size],a[i])<eps)
stiv2_size--;
stiv2[++stiv2_size]=a[i];
}
g<<setprecision(6)<<fixed; /// fixam precizia zecimalelor la 6
g<<stiv1_size+stiv2_size-2<<'\n';
for (i=1;i<=stiv1_size;i++)
g<<stiv1[i].x<<" "<<stiv1[i].y<<'\n';
for (i=2;i<stiv2_size;i++)
g<<stiv2[i].x<<" "<<stiv2[i].y<<'\n';
return 0;
}