Pagini recente » Cod sursa (job #2302960) | Cod sursa (job #573152) | Cod sursa (job #371766) | Cod sursa (job #2593409) | Cod sursa (job #3222528)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct puncte
{
double x, y;
};
puncte v[130001];
vector <puncte>st;
bool comp(puncte a, puncte b)
{
double x = v[1].x,
y = v[1].y;
return (a.y - y) * (b.x - x) < (a.x - x) * (b.y - y);
}
double determinant(puncte a, puncte b)
{
return a.x * b.y - b.x * a.y;
}
int orientare(puncte a, puncte b, puncte c)
{
int ras = determinant(a, b) + determinant(b, c) + determinant(c, a);
if(ras > 0)return 1;
else
if(ras < 0)
return -1;
return 0;
}
int main()
{
int n;
f >> n;
for(int i = 1; i <= n; i++)
{
f >> v[i].x >> v[i].y;
if(v[i].y < v[1].y)
swap(v[1], v[i]);
}
sort(v + 2, v + n + 1, comp);
st.push_back(v[1]);
st.push_back(v[2]);
for(int i = 3; i <= n; i++)
{
while(st.size() > 1 && orientare(st[st.size() - 2], st[st.size() - 1], v[i]) != 1)
st.pop_back();
st.push_back(v[i]);
}
g << st.size() << '\n';
for(int i = 0; i < st.size(); i++)
{
g << fixed << setprecision(6) << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}
/*
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct nume
{
double x, y;
};
nume v[120001];
double minx = 1e9, miny = 1e9;
vector <nume>st;
bool comp(nume a, nume b)
{
return (-minx + a.x) * (-miny + b.y) > (-miny + a.y) * (-minx + b.x);
}
double determinant(nume a, nume b)
{
return a.x * b.y - a.y * b.x;
}
int orientare(nume a, nume b, nume c)
{
double val = determinant(a, b) + determinant(b, c) + determinant(c, a);
if(val > 0)
return 1;
else
if(val == 0)
return 2;
else
return 3;
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
///
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> v[i].x >> v[i].y;
if(v[i].y < miny)
{
miny = v[i].y;
minx = v[i].x;
swap(v[1], v[i]);
}
}
sort(v + 2, v + n + 1, comp);
st.push_back(v[1]);
st.push_back(v[2]);
for(int i = 3; i <= n; i++)
{
while(st.size() > 1 && orientare(st[st.size() - 2], st[st.size() - 1], v[i]) != 1)
st.pop_back();
st.push_back(v[i]);
}
cout << st.size() << '\n';
for(int i = 0; i < st.size(); i++)
{
cout << fixed << setprecision(6) << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}
*/