Pagini recente » Cod sursa (job #854864) | Cod sursa (job #1626397) | Cod sursa (job #1614881) | Clasament qwertyytrewq | Cod sursa (job #2380896)
#include <bits/stdc++.h>
using namespace std;
struct punct
{
long double x, y;
}v[120005], minn, val1, val2, w[120005];
int cadran(punct a)
{
if(a.x > minn. x && a.y >= minn.y)return 1;
if(a.x <= minn.x && a.y > minn.y)return 2;
if(a.x < minn.x && a.y <= minn.y)return 3;
if(a.x >= minn.x && a.y < minn.y)return 4;
}
int aria(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
bool cmp(punct a, punct b)
{
int c1 = cadran(a);
int c2 = cadran(b);
if(c1 == c2)
{
int det = aria(minn, a, b);
if(det < 0)return false;
return true;
}
return c1 < c2;
}
bool stanga(punct a, punct b, punct c)
{
val1.x = b.x - a.x;
val1.y = b.y - a.y;
val2.x = c.x - a.x;
val2.y = c.y - a.y;
int rez = val1.x * val2.y - val1.y * val2.x;
if(rez > 0)return true;
return false;
}
int n, i, k;
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> n;
for(i = 1; i <= n; i ++)
{
f >> v[i].x >> v[i].y;
if(v[i].y < minn.y)minn = v[i];
else if(v[i].y == minn.y && v[i].x < minn.x)minn = v[i];
}
sort(v + 1, v + n + 1, cmp);
v[n + 1] = v[1];
w[1] = v[1];
w[2] = v[2];
k = 2;
i = 2;
while(w[k].x != v[1].x || w[k].y != v[1].y)
{
i++;
while(k > 1 && !stanga(v[i], w[k - 1], w[k]))k--;
w[++k] = v[i];
}
g << k - 1 << "\n";
for(i = 1; i < k; i ++)
g << setprecision(12) << fixed << w[i].x << " " << w[i].y << "\n";
return 0;
}