Pagini recente » Cod sursa (job #2049001) | Cod sursa (job #2662240) | Cod sursa (job #3134638) | Cod sursa (job #1802326) | Cod sursa (job #2556996)
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#define EPSILON 0.000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x, y;
bool operator !=(punct other)
{
return fabs(x - other.x)>EPSILON || fabs(y - other.y)>EPSILON;
}
} pcte[120005];
double orientation(punct a, punct b, punct c)
{
return (b.y-a.y)*(c.x-a.x) - (c.y-a.y)*(b.x-a.x);
}
int n, start;
bool cmp(punct a, punct b)
{
double o = orientation(pcte[start], a, b);
if(o < 0)
return true;
return false;
}
void read()
{
f>>n;
f>>pcte[0].x>>pcte[0].y;
for(int i = 1; i<n; ++i)
{
f>>pcte[i].x>>pcte[i].y;
if(pcte[start].x > pcte[i].x || (pcte[start].x == pcte[i].x && pcte[start].y > pcte[i].y))
{
start = i;
}
}
swap(pcte[start], pcte[0]);
start = 0;
sort(pcte+1, pcte+n, cmp);
}
punct S[120005];
int len = 0;
void solve()
{
for(int index = 0; index < n; ++index)
{
while(len >= 2 && orientation(S[len-1], pcte[index], S[len-2]) > 0)
{
len--;
}
S[len++] = pcte[index];
}
}
void print()
{
g<<len<<"\n";
for(int i = 1; i<len; ++i)
{
g<<S[i].x<<" "<<S[i].y<<"\n";
}
g<<S[0].x<<" "<<S[0].y<<"\n";
}
int main()
{
read();
solve();
print();
return 0;
}