Pagini recente » Cod sursa (job #181730) | Cod sursa (job #1016584) | Cod sursa (job #3040053) | Cod sursa (job #342169) | Cod sursa (job #2286776)
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <stack>
#define eps 1e-14
using namespace std;
struct punct{
double x,y;
void print()
{
printf("%.6lf %.6lf\n",x,y);
}
};
vector<punct>path,v,sol;
stack<int>st;
double dist(punct a,punct b)
{
return sqrt(1.0*(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y)));
}
int orientare(punct a,punct b,punct c)
{
double val = 1.0*(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
if(val >= -eps && val <= eps)
return 0;
if(val < -eps)
return -1;
else
return 1;
}
void interschimba(punct a,punct b)
{
punct aux;
aux = a;
a = b;
b = aux;
}
int penult()
{
int temp = st.top();
int aux;
st.pop();
aux = st.top();
st.push(temp);
return aux;
}
punct start;
bool cmp(punct a,punct b)
{
if(orientare(start,a,b) == 0)
return dist(start,a)<dist(start,b);
if(orientare(start,a,b) == 1)
return 0;
return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,x,y;
scanf("%d",&n);
int pos;
double xm=2000000000,ym=2000000000;
for(int i = 1 ; i <= n ; i ++)
{
scanf("%lf%lf",&x,&y);
punct temp;
temp.x = x;
temp.y = y;
v.push_back(temp);
if(ym - y > eps)
{
ym = y;
xm = x;
pos = i;
continue;
}
if(fabs(ym-y)<eps)
{
if(fabs(xm-x))
{
x = xm;
y = ym;
pos = i;
continue;
}
}
}
interschimba(v[0],v[pos-1]);
start = v[0];
sort(v.begin()+1,v.end(),cmp);
int dim = -1;
path.push_back(start);
for(int i = 1 ; i < v.size() ; i++)
{
while(i < v.size()-1 && orientare(start,v[i],v[i+1]) == 0)
i++;
path.push_back(v[i]);
}
st.push(0);
int i = 1;
while(i < path.size())
{
if(orientare(path[penult()],path[st.top()],path[i]) == 1)
st.push(i++);
else
st.pop();
}
while(!st.empty())
{
sol.push_back(path[st.top()]);
st.pop();
}
printf("%d\n",sol.size());
for(int i = 0 ; i < sol.size() ; i++)
sol[i].print();
return 0;
}