Pagini recente » Cod sursa (job #971028) | Cod sursa (job #35002) | Cod sursa (job #2610195) | Cod sursa (job #1832546) | Cod sursa (job #2154545)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <algorithm>
#define maxN 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef struct{
double x;
double y;
}point;
point v[maxN], stiva[maxN];
int n, h;
double det(point a, point b, point c)
{
return (a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y);
}
double dist(point a, point b)
{
double dist;
dist = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
return dist;
}
int comparare(point a, point b)
{
if(a.x == b.x && a.y == b.y)
return 0;
return 1;
}
bool compare_determinant(const point a, const point b)
{
if(det(a,b, v[1]) > 0)
{
return true;
}
if(det(a,b, v[1]) < 0)
{
return false;
}
if(det(a,b, v[1]) == 0)
{
return ((dist(v[1], a) < dist(v[1],b)));
}
}
int extrem()
{
point rez;
rez.x = 0;
rez.y = 0;
double minim = 9999999999;
int poz;
for(int i = 1; i <= n; i++)
{
if(v[i].x == minim)
{
if(v[i].y < rez.y)
{
rez.x = v[i].x;
rez.y = v[i].y;
poz = i;
}
}
if(v[i].x < minim)
{
minim = v[i].x;
rez.x = v[i].x;
rez.y = v[i].y;
poz = i;
}
}
return poz;
}
int main()
{
f >> n;
point aux;
int poz, k = 0, i;
for(i = 1; i <= n; i++)
{
f >> v[i].x >> v[i].y;
}
poz = extrem();
if(poz != 1)
{
aux.x = v[1].x;
aux.y = v[1].y;
v[1].x = v[poz].x;
v[1].y = v[poz].y;
v[poz].x = aux.x;
v[poz].y = aux.y;
}
sort(v+2, v+n+1, compare_determinant);
for(i = 1; i <= n ;i++)
{
while(k >= 2)
{
k--;
if(det(stiva[k], stiva[k+1],v[i]) <= 0)
continue;
k++;
break;
}
k++;
stiva[k].x = v[i].x;
stiva[k].y = v[i].y;
}
g << k << '\n';
for(i = 1 ; i <= k; i++)
{
g << setprecision(12) << fixed <<stiva[i].x << " " << stiva[i].y << '\n';
}
}