Pagini recente » Cod sursa (job #66102) | Cod sursa (job #565291) | Cod sursa (job #2160904) | Cod sursa (job #1642478) | Cod sursa (job #3223501)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct pct{
double x, y;
};
const int mxN = 120001;
int n, k = 0;
pct sir[mxN], ans[mxN];
void citire(){
fin >> n;
for(int i = 1; i <= n; i++){
fin >> sir[i].x >> sir[i].y;
}
}
double orientare(pct a, pct b, pct c){
//mBC > mAB
//(yc - yb) / (xc - xb) > (yb - ya) / (xb - xa)
//(yc - yb) * (xb - xa) - (xc - xb) * (yb - ya) > 0
return (c.y - b.y) * (b.x - a.x) - (b.y - a.y) * (c.x - b.x);
}
bool crtSort(pct a, pct b){
if(orientare(sir[1], a, b) > 0)
return true;
return false;
}
void sortare(){
int indMin = 1;
for(int i = 2; i <= n; i++)
if(sir[indMin].y > sir[i].y || (sir[indMin].y == sir[i].y && sir[indMin].x > sir[i].x))
indMin = i;
swap(sir[indMin], sir[1]);
sort(sir + 2, sir + 1 + n, crtSort);
/*
for(int i = 2; i <= n; i++){
double t = (sir[i].y - sir[1].y) / (sir[i].x - sir[1].x);
fout << t << "\n";
}
*/
}
void convexHull(){
ans[++k] = sir[1];
ans[++k] = sir[2];
for(int i = 3; i <= n; i++){
while(orientare(ans[k], ans[k - 1], sir[i]) > 0){
k--;
}
ans[++k] = sir[i];
}
}
void afisare(){
fout << k << "\n";
for(int i = 1; i <= k; i++){
fout << setprecision(20) << ans[i].x << " " << ans[i].y << "\n";
}
}
int main()
{
citire();
sortare();
convexHull();
afisare();
return 0;
}