Pagini recente » Cod sursa (job #1325607) | Cod sursa (job #814675) | Cod sursa (job #819495) | Cod sursa (job #2624229) | Cod sursa (job #3247716)
#include<bits/stdc++.h>
using namespace std;
int n,poz[200000],rez[200000],cnt=0;
stack<int> q;
struct twin{
float x;
float y;
};
bool compare(twin x,twin y)
{
if(x.x==y.x)
return x.y<y.y;
else
return x.x<y.x;
}
float det(float x1,float y1,float x2,float y2,float x3,float y3)
{
return x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
}
twin a[200000];
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,compare);
for(int i=2;i<n;i++)
if(det(a[1].x,a[1].y,a[n].x,a[n].y,a[i].x,a[i].y)<0)
poz[i]=1;
q.push(1);
for(int i=2;i<=n;i++)
if(poz[i]||i==n)
{
int hold=q.top();
q.pop();
int x;
if(q.size()>0)
x=q.top();
while(q.size()>1&&det(a[x].x,a[x].y,a[i].x,a[i].y,a[hold].x,a[hold].y)>0.0){
hold=x;
q.pop();
if(!q.empty())
x=q.top();
}
q.push(hold);
q.push(i);
}
while(!q.empty())
{
if(!rez[q.top()])
cnt++;
rez[q.top()]=1;
q.pop();
}
///
q.push(n);
for(int i=n-1;i>=1;i--)
if(!poz[i]||i==1)
{
int hold=q.top();
q.pop();
int x;
if(q.size()>0)
x=q.top();
while(q.size()>1&&det(a[x].x,a[x].y,a[i].x,a[i].y,a[hold].x,a[hold].y)>0.0){
hold=x;
q.pop();
if(!q.empty())
x=q.top();
}
q.push(hold);
q.push(i);
}
while(!q.empty())
{
if(!rez[q.top()])
cnt++;
rez[q.top()]=1;
q.pop();
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++)
if(rez[i])
cout<<a[i].x<<" "<<a[i].y<<endl;
}