Pagini recente » Cod sursa (job #1934112) | Cod sursa (job #1275410) | Cod sursa (job #785154) | Cod sursa (job #617009) | Cod sursa (job #3247535)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<stack>
using namespace std;
stack<int> varf;
int n;
const double t=1000000000.;
struct coordonate
{
double X;
double Y;
///short verif=0;
}cuie[120000];
bool compareCoordinates(coordonate a, coordonate b)
{
if(a.X!=b.X)
return a.X<b.X;
if(a.Y!=b.Y)
return a.Y<b.Y;
}
double arie(coordonate a, coordonate b, coordonate c)
{
double A=a.X*b.Y+b.X*c.Y+c.X*a.Y-c.X*b.Y-a.X*c.Y-b.X*a.Y;
return A;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin>>n;
for(int i=0; i<n; ++i)
{
fin>>cuie[i].X>>cuie[i].Y;
cutie[i].X+=t;
cutie[i].Y+=t;
}
sort(cuie, cuie+n, compareCoordinates);
int ok;
varf.push(0);
///cuie[0].verif=1;
varf.push(1);
if(arie(cuie[0], cuie[n-1], cuie[1])>=0.)
ok=1;
else
ok=-1;
///cuie[1].verif=1;
for(int i=2; i<n-1; ++i)
{
if(arie(cuie[0], cuie[n-1], cuie[i])*ok>=0.)
{
while(arie(cuie[varf[varf.size()-2]], cuie[varf[varf.size()-1]], cuie[i])*ok>=0.)
{
varf.pop();
if(varf.size()<2)
break;
}
varf.push(i);
}
///cuie[i].verif=1;
}
varf.push(n-1);
for(int i=2; i<n-1; ++i)
{
if(arie(cuie[0], cuie[n-1], cuie[i])*ok<0.)
{
while(arie(cuie[varf[varf.size()-2]], cuie[varf[varf.size()-1]], cuie[i])*ok>=0.)
{
varf.pop();
if(varf.size()<2)
break;
}
varf.push(i);
}
///cuie[i].verif=1;
}
/*for(int i=0; i<n; ++i)
cout<<cuie[i].X<<' '<<cuie[i].Y<<'\n';*/
fin.close();
fout.close();
return 0;
}