Cod sursa(job #2552803)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 21 februarie 2020 11:13:27
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int N = 120000;

struct punct{
	double x, y;
} coord[N];

vector <punct> stiva1;
vector <punct> stiva2;

bool cmp(punct a, punct b){
	if(a.y <= b.y)
		return true;
	return false;
}

double getArea(punct a, punct b, punct c){
	double area = a.x * (b.y - c.y) - b.x * (a.y - c.y) + c.x * (a.y - b.y);
	return area;
}

int main()
{
	int n,i,top1,top2;
	double area;
	fin >> n;
	for(i=0; i<n; i++)
		fin >> coord[i].x >> coord[i].y;
	sort(coord, coord+n, cmp);
	stiva1.push_back(coord[0]);
	stiva2.push_back(coord[0]);
	for(i=1; i<n; i++){
		area = getArea(coord[0], coord[n-1], coord[i]);
		if(area <= 0){	/// dreapta
			top2 = (int)stiva2.size();
			while(top2 > 1 && getArea(stiva2[top2-2], stiva2[top2-1], coord[i]) <= 0){
				stiva2.pop_back();
				top2--;
			}
			stiva2.push_back(coord[i]);
		}
		if(area >= 0){	/// stanga
			top1 = (int)stiva1.size();
			while(top1 > 1 && getArea(stiva1[top1-2], stiva1[top1-1], coord[i]) >= 0){
				stiva1.pop_back();
				top1--;
			}
			stiva1.push_back(coord[i]);
		}
	}
	top1 = (int)stiva1.size();
	top2 = (int)stiva2.size();
	fout << top1 + top2 - 2 << "\n";
	fout << setprecision(6) << fixed;
	for(i=0; i<top1; i++)
		fout << stiva1[i].x << " " << stiva1[i].y << "\n";
	for(i = top2 - 2; i > 0; i--)
		fout << stiva2[i].x << " " << stiva2[i].y << "\n";
	return 0;
}