Pagini recente » Cod sursa (job #1910223) | Cod sursa (job #1341758) | Cod sursa (job #1270763) | Cod sursa (job #2505400) | Cod sursa (job #2558197)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, ok, s[120005];
bool viz[120005];
struct Point
{
double x, y;
}v[120005];
inline bool cmp(const Point &a, const Point &b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
double rez(Point A, Point B, Point C)
{
return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}
int top;
void rezolva()
{
s[1] = 1;
s[2] = 2;
top = 2;
viz[2] = true;
int i = 3;
int pas = 1;
while(!viz[1])
{
while(viz[i])
{
if(i == n)
pas = -1;
i += pas;
}
while(rez(v[s[top - 1]],v[s[top]],v[i]) < 0 && top >= 2)
viz[s[top]] = 0, top--;
s[++top] = i;
viz[i] = 1;
}
top --;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
rezolva();
fout << top << '\n';
for(int i = 2; i <= top + 1; i++)
fout << fixed << setprecision(8) << v[s[i]].x << " " << fixed << setprecision(8) << v[s[i]].y <<'\n';
return 0;
}