Pagini recente » Cod sursa (job #2570360) | Cod sursa (job #476330) | Cod sursa (job #2202570) | Cod sursa (job #2500591) | Cod sursa (job #1509834)
#include <bits/stdc++.h>
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 dreapta
{
while (stiv1_size>=2 && cross_product(stiv1[stiv1_size-1],stiv1[stiv1_size],a[i])<0)
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--)
{
while (stiv2_size>=2 && cross_product(stiv2[stiv2_size-1],stiv2[stiv2_size],a[i])<0)
stiv2_size--;
stiv2[++stiv2_size]=a[i];
}
g<<setprecision(6)<<fixed;
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;
}