Pagini recente » Cod sursa (job #2725372) | Istoria paginii utilizator/butnaru_vlad | Cod sursa (job #1741409) | Cod sursa (job #633761) | Cod sursa (job #2383529)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct
{
double x, y;
}st[120001], v[120001];
int det(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;
}
bool cmp(punct a, punct b)
{
if(a.y<b.y)
return true;
else if(a.y>b.y)
return false;
else
{
if(a.x<b.x)
return true;
return false;
}
}
/*bool cmp2(punct a, punct b)
{
if(a.y>b.y)
return true;
else if(a.y<b.y)
return false;
else
{
if(a.x>b.x)
return true;
return false;
}
}*/
/*void parcurg()
{
sort(st+1, st+n+1, cmp);
int c = 2;
v[1] = st[1];
while(c != n)
{
if(det(st[1], st[n], st[c])<0)
{
v[++nr] = st[c];
if(c>2 && det(st[c-2], st[c-1], st[c])<0)
{
v[nr-1] = v[nr];
--nr;
}
}
c++;
}
while(c != 1)
{
if(det(st[1], st[n], st[c])>0)
{
v[++nr] = st[c];
if(c<n-1 && det(st[c+2], st[c+1], st[c])<0)
{
v[nr-1] = v[nr];
--nr;
}
}
c--;
}
}*/
int main()
{
int n, nr = 1, k = 0;
in>>n;
for(int i = 1; i<=n; i++)
{
in>>st[i].x>>st[i].y;
}
sort(st+1, st+n+1, cmp);
int c = 2;
v[1] = st[1];
while(c != n)
{
if(det(st[1], st[n], st[c])<0)
{
v[++nr] = st[c];
if(nr>2 && det(v[nr-2], v[nr-1], v[nr])<0)
{
v[nr-1] = v[nr];
--nr;
}
}
c++;
}
v[++nr] = st[n];
while(c != 1)
{
if(det(st[1], st[n], st[c])>0)
{
v[++nr] = st[c];
++k;
if(k>2 && det(v[nr-2], v[nr-1], v[nr])<0)
{
v[nr-1] = v[nr];
--nr;
}
}
c--;
}
out<<nr<<endl;
for(int i = 1; i<=nr; i++)
out<<setiosflags(ios::showpoint)<<v[i].x<<" "<<v[i].y<<'\n';
return 0;
}