Pagini recente » Cod sursa (job #564456) | Cod sursa (job #1102841) | Cod sursa (job #1845537) | Cod sursa (job #2160245) | Cod sursa (job #1829844)
#include <fstream>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,l,A,B;
struct punct
{
double x,y;
int o;
} p[120001],pa,pb;
int compare(punct a,punct b)
{
return (a.y<b.y);
}
stack <punct> s,S;
double determinant(punct A,punct B,punct C)
{
return A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - A.x * C.y - B.x * A.y;
}
int sensTriunghi(punct A,punct B,punct C)
{
if (determinant(A,B,C) < 0)
{
return -1;
}
else
{
return 1;
}
}
int main()
{
fin>>n;
for(i=1; i<=n; i++)
{
fin>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1,compare);
for(i=1; i<=n; i++) p[i].o=i;
s.push(p[1]);
s.push(p[2]);
l=2;
for(i=3; i<=n; i++)
{
pa=s.top();
s.pop();
pb=s.top();
s.push(pa);
if(sensTriunghi(pb,pa,p[i])==1)s.push(p[i]),l++;
else
{
while(sensTriunghi(pb,pa,p[i])!=1&&l>1)
{
s.pop();
l--;
if(l!=1)
{
pa=s.top();
s.pop();
pb=s.top();
s.push(pa);
}
}
s.push(p[i]);
l++;
}
}
S.push(p[1]);
S.push(p[2]);
l=2;
for(i=3; i<=n; i++)
{
pa=S.top();
S.pop();
pb=S.top();
S.push(pa);
if(sensTriunghi(pb,pa,p[i])==-1)S.push(p[i]),l++;
else
{
while(sensTriunghi(pb,pa,p[i])!=-1&&l>1)
{
S.pop();
l--;
if(l!=1)
{
pa=S.top();
S.pop();
pb=S.top();
S.push(pa);
}
}
S.push(p[i]);
l++;
}
}
int h=0;
fout<<s.size()+S.size()-2<<'\n';
while(!s.empty())
{
p[++h]=s.top();
s.pop();
}
for(h=h;h>0;h--)
fout<<p[h].x<<" "<<p[h].y<<'\n';
while(!S.empty())
{
p[++h]=S.top();
S.pop();
}
for(i=2;i<h;i++)
fout<<p[i].x<<" "<<p[i].y<<'\n';
fin.close();
fout.close();
return 0;
}