Pagini recente » Cod sursa (job #599233) | Cod sursa (job #3292555) | Cod sursa (job #2924346) | Cod sursa (job #1209500) | Cod sursa (job #2662429)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120005;
struct Point
{
double x,y;
bool operator<(const Point&other)const
{
if(x!=other.x)
return x<other.x;
return y<other.y;
}
};
stack<int>rez;
Point v[NMAX];
bitset<NMAX>viz;
int n;
void citire()
{
fin>>n;
for(int i=0;i<n;i++)
fin>>v[i].x>>v[i].y;
}
int det_orientare(Point a,Point b,Point c)
{
double det=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
if(det<0)
return -1;
if(det>0)
return 1;
return 0;
}
void solve()
{
rez.push(0);
viz[0]=true;
rez.push(1);
viz[1]=true;
for (int i=2;i<n;i++)
{
int k=rez.top();
rez.pop();
viz[k]=false;
while(det_orientare(v[rez.top()],v[k],v[i])>0)
{
k=rez.top();
rez.pop();
viz[k]=false;
if(rez.empty())
break;
}
rez.push(k);
rez.push(i);
viz[k]=viz[i]=true;
}
rez.pop();
viz[n-1]=viz[0]=false;
rez.push(n-1);
rez.push(n-2);
for(int i=n-3;i>=0;i--)
{
if(viz[i]==true)
continue;
int k=rez.top();
rez.pop();
viz[k]=false;
while(det_orientare(v[rez.top()],v[k],v[i])>0)
{
k=rez.top();
rez.pop();
viz[k]=false;
if(rez.empty())
break;
}
rez.push(k);
rez.push(i);
viz[k]=viz[i]=true;
}
}
void afish()
{
int nr{0};
rez.pop();
fout<<rez.size()<<" ";
while (!rez.empty())
{
int top=rez.top();
fout<<setprecision(6)<<fixed<<v[top].x <<" "<<v[top].y <<"\n";
rez.pop();
}
}
int main()
{
citire();
sort(v,v+n);
solve();
afish();
return 0;
}