Pagini recente » Cod sursa (job #2360242) | Cod sursa (job #229023) | Cod sursa (job #1441259) | Cod sursa (job #1398431) | Cod sursa (job #2119648)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int Nmax = 120005;
int n , st[Nmax] , top;
struct P
{
double ox , oy;
};
P a[Nmax];
bool viz[Nmax]; /// viz[i] = true => punctul i se afla in infasuratorare convexa
/// Sortez crescator dupa coordonata oy si in caz de egalitate crescator dupa coordonata ox
inline bool CMP(P A , P B)
{
if(A . oy == B . oy)
return A . ox < B . ox;
return A . oy < B . oy;
}
/// verific in ce cadran se afla punctul cu numarul k fata de dreapta determinata de punctele cu numarul i respectiv j
/// 0 = sunt coliniatre , > 0 se afla in cadranul + , < 0 se afla in cadranul -
inline double CHECK(int i , int j , int k)
{
return a[k] . ox * (a[i] . oy - a[j] . oy) + a[k] . oy * (a[j] . ox - a[i] . ox)
+ a[i] . ox * a[j] . oy - a[j] . ox * a[i] . oy;
}
inline void Solve()
{
++top;
st[top] = 1;
viz[top] = true;
++top;
st[top] = 2;
viz[top] = true;
for(int i = 3 ; i <= n ; i++)
if(!viz[i]) /// verific daca nu se afla in infasuratoare
{
if(top > 1 && CHECK(st[top - 1] , st[top] , i) < 0)
{
viz[st[top]] = false;
top--;
}
++top;
st[top] = i;
viz[i] = true;
}
for(int i = n - 1 ; i >= 1 ; i--)
if(!viz[i])
{
if(top > 1 && CHECK(st[top - 1] , st[top] , i) < 0)
{
viz[st[top]] = false;
top--;
}
++top;
st[top] = i;
viz[i] = true;
}
fout << top - 1 << "\n";
for(int i = 1 ; i < top ; i++)
fout << fixed << setprecision(6) << a[st[i]] . ox << " " << a[st[i]] . oy << "\n";
}
int main()
{
fin >> n;
for(int i = 1 ; i <= n ; i++)
fin >> a[i] . ox >> a[i] . oy;
sort(a + 1 , a + n + 1 , CMP);
Solve();
fin.close();
fout.close();
return 0;
}