Pagini recente » Cod sursa (job #2926525) | Cod sursa (job #1667966) | Cod sursa (job #490488) | Cod sursa (job #2201179) | Cod sursa (job #1499845)
#include <bits/stdc++.h>
#define pub push_back
#define pob pop_back
using namespace std;
double x,y;
int n;
struct punct
{
double x,y;
} D[125000];
vector <punct> sus,jos;
bool cmp(punct A,punct B)
{
if (A.x==B.x)
return A.y<B.y;
return A.x<B.x;
}
void citire()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (int i=1; i<=n; ++i)
{
scanf("%lf%lf",&D[i].x,&D[i].y);
}
sort(D+1,D+n+1,cmp);
}
double det(punct A,punct B,punct C)
{
return ((B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y));
}
int main()
{
citire();
int i;
sus.pub(D[1]);
sus.pub(D[2]);
jos.pub(D[1]);
jos.pub(D[2]);
for (int i=3; i<=n; ++i)
{
int sm=sus.size();
while (sm>=2 && det(sus[sm-2],sus[sm-1],D[i])>0) ///creez infasuratoarea de sus, sterg pana cand gasesc
///un punct care face graficul sa rastoarne apa
{
sus.pob();
--sm;
}
sus.pub(D[i]);
int jm=jos.size();
while (jm>=2 && det(jos[jm-2],jos[jm-1],D[i])<0) ///creez graficul astfel incat sa tina apa
{
jos.pob();
--jm;
}
jos.pub(D[i]);
}
if (sus[0].x==jos[0].x && jos[0].y==sus[0].y)
jos.erase(jos.begin());
if (sus[sus.size()-1].x==jos[jos.size()-1].x && jos[jos.size()-1].y==sus[sus.size()-1].y)
jos.pob();
printf("%d\n",sus.size()+jos.size());
for(i=0; i<jos.size(); i++)
printf("%lf %lf\n",jos[i].x,jos[i].y);
for(i=sus.size()-1; i>=0; i--)
printf("%lf %lf\n",sus[i].x,sus[i].y);
return 0;
}