Pagini recente » Cod sursa (job #858777) | Cod sursa (job #1605480) | Cod sursa (job #1995970) | Cod sursa (job #887959) | Cod sursa (job #559656)
Cod sursa(job #559656)
#include<fstream>
#include<stack>
#include<algorithm>
#define dmax 120010
using namespace std;
typedef struct punct
{
double x,y;
} punct;
punct p[dmax];
int n,k;
int s[dmax];
bool v[dmax];
void citire()
{
int i;
ifstream fin("infasuratoare.in");
fin>>n;
for (i=1; i<=n; i++)
fin>>p[i].x>>p[i].y;
fin.close();
}
bool comp(punct a, punct b)
{
if (a.y == b.y)
return a.x < b.x; else
return a.y < b.y;
}
int aria(int a, int b, int c)
{
if (p[a].x * p[b].y + p[c].x * p[a].y + p[b].x * p[c].y - p[c].x * p[b].y - p[a].x * p[c].y - p[b].x * p[a].y < 0)
return -1;
return 0;
}
void solve()
{
int i;
s[1] = 1; s[2] = 2;
k = 2;
for (i=3; i<=n; i++)
{
while (k > 1 && aria(s[k-1], s[k], i) < 0)
{
v[s[k]] = 0;
k--;
}
k++;
s[k] = i;
v[i] = 1;
}
for (i=n; i>=1; i--)
if (v[i] == 0)
{
while (k > 1 && aria(s[k-1], s[k], i) < 0)
{
v[s[k]] = 0;
k--;
}
k++;
s[k] = i;
v[i] = 1;
}
}
void afisare()
{
int i;
ofstream fout("infasuratoare.out");
fout<<k-1<<'\n';
fout.setf(ios::fixed);
fout.precision(6);
for (i=1; i<=k-1; i++)
fout<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
fout.close();
}
int main()
{
citire();
sort(p+1,p+n+1,comp);
solve();
afisare();
return 0;
}