Pagini recente » Cod sursa (job #1952736) | Cod sursa (job #1986232) | Cod sursa (job #321114) | Cod sursa (job #3233633) | Cod sursa (job #2659568)
#include <fstream>
#include <vector>
#define EPSILON 0.0000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x, y;
bool operator==(const point other) const
{
return x == other.x && y == other.y;
}
bool operator!=(const point other) const
{
return x != other.x || y != other.y;
}
};
int n;
point a[120005];
vector<point> rez;
double directie(point a, point b, point c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
void citire()
{
f>>n;
int pctmin = 0;
for(int i = 0; i<n; i++)
{
f>>a[i].x>>a[i].y;
if(a[i].x < a[pctmin].x)
pctmin = i;
}
rez.push_back(a[pctmin]);
}
void rezolvare()
{
point referinta;
if(rez[0] == a[0])
referinta = a[1];
else
referinta = a[0];
for(int i = 1; i<n; i++)
{
if(a[i] != referinta && a[i] != rez[0])
{
if(directie(rez[0], referinta, a[i]) < 0)
referinta = a[i];
}
}
rez.push_back(referinta);
for(int j = 1; rez.back() != rez.front(); j++)
{
referinta = rez[0];
for(int i = 1; i<n; i++)
{
if(a[i] != referinta && a[i] != rez[j])
{
if(directie(rez[j], referinta, a[i]) < 0)
referinta = a[i];
}
}
rez.push_back(referinta);
}
}
void afisare()
{
g<<rez.size()-1<<"\n";
for(int i = 0; i<rez.size()-1; i++)
{
g<<rez[i].x<<" "<<rez[i].y<<"\n";
}
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}