Pagini recente » Cod sursa (job #812048) | Cod sursa (job #1143103) | Cod sursa (job #2650974) | Cod sursa (job #17750) | Cod sursa (job #2145525)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int Nmax = 120005;
struct Point
{
double x, y;
};
Point a[Nmax];
int st[Nmax], top, n;
bool viz[Nmax];
inline bool CMP(const Point A, const Point B)
{
if(A . y == B . y)
return A . x < B . x;
return A . y < B . y;
}
/// verific in ce cadran se afla punctul cu numarul k de dreapta determinata de punctele cu numarul i respectiv
/// j
inline bool CHECK(int i, int j, int k)
{
return (a[i] . x * a[j] . y + a[i] . y * a[k] . x + a[j] . x * a[k] . y
- a[j] . y * a[k] . x - a[j] . x * a[i] . y - a[k] . y * a[i] . x) < 0;
}
inline void HILL()
{
++top;
st[top] = 1;
++top;
st[top] = 2;
viz[2] = true;
for(int i = 3 ; i <= n ; i++)
{
while(top > 1 && CHECK(st[top - 1], st[top], i))
{
viz[st[top]] = false;
top--;
}
++top;
st[top] = i;
viz[i] = true;
}
/// inchid poligonul
for(int i = n ; i >= 1 ; i--)
if(!viz[i]) /// nu se afla in infasuratoare
{
while(top > 1 && CHECK(st[top - 1], st[top], i))
{
viz[st[top]] = false;
top--;
}
++top;
st[top] = i;
viz[i] = true;
}
fout << top - 1 << "\n"; /// iau primul punct de doua ori(odata si cand inchid poligonul)
for(int i = 1 ; i < top ; i++)
fout << fixed << setprecision(6) << a[st[i]] . x << " " << a[st[i]] . y << "\n";
}
int main()
{
fin >> n;
for(int i = 1 ; i <= n ; i++)
fin >> a[i] . x >> a[i] . y;
sort(a + 1, a + n + 1, CMP);
HILL();
fin.close();
fout.close();
return 0;
}