Pagini recente » Cod sursa (job #2217481) | Cod sursa (job #2129927) | Cod sursa (job #1745511) | Cod sursa (job #2179334) | Cod sursa (job #2834878)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n;
struct pct{
double x,y;
}puncte[120001],punt_jos_stanga;
vector<pct>infasuratoare;
double determinant(pct a,pct b,pct c)
{
return ((a.x*b.y) + (a.y*c.x) + (b.x*c.y) - (b.y*c.x) - (c.y*a.x) - (a.y*b.x));
}
bool comp(pct a,pct b)
{
//https://sites.google.com/site/centrulinfo1/materiale-video/algoritmi-video/infasuratoarea-convexa
// daca determinantul este mai mare de 0 inseamna ca b are unghiul mai mare cu punct_jos_stanga decat a
if(determinant(punt_jos_stanga,a,b)>0)
return true;
return false;
}
void init()
{
sort(puncte+2,puncte+1+n,comp);
}
bool sens_ceasornic(pct a,pct b,pct c)
{
// daca punctul pe care vrem sa il adaugam sa afla in rotire in sens ceasornic cu ultimele 2 puncte dam pop la punctele din vector
// pana sensul va fi in sens trigonometric
//scoatem si in caz ca e egal cu 0 (coliniare) deoarece incercam sa minimizam numarul de puncte
// asa ca nu ar avea sens sa luam pe ambele deoarece unul se afla pe conturul poligonului
if(determinant(a,b,c)<=0)
return true;
return false;
}
void alg()
{
infasuratoare.push_back(punt_jos_stanga);
infasuratoare.push_back(puncte[2]);
for(int i = 3;i<=n;i++)
{
while(sens_ceasornic(infasuratoare[infasuratoare.size()-2],infasuratoare[infasuratoare.size()-1],puncte[i]))
infasuratoare.pop_back();
infasuratoare.push_back(puncte[i]);
}
}
void afisare()
{
g << infasuratoare.size()<< endl;
for(int i = 0;i<infasuratoare.size();i++)
g << fixed<<setprecision(6)<< infasuratoare[i].x << " "<< infasuratoare[i].y<< '\n';
}
void citire()
{
punt_jos_stanga.x = 2000000000.00;
punt_jos_stanga.y = 2000000000.00;
int indice;
f >> n;
for(int i= 1;i<=n;i++)
{
f >> puncte[i].x >> puncte[i].y;
//gasim cel mai de jos punct, iar daca sunt mai multe la fel de jos cel mai din stanga
// suntem siguri ca acel punct apartine infasuratorii, asa ca de acolo incepem algoritmul
if(puncte[i].y<punt_jos_stanga.y)
{
punt_jos_stanga.x = puncte[i].x;
punt_jos_stanga.y = puncte[i].y;
indice = i;
}
else
if(puncte[i].y==punt_jos_stanga.y && puncte[i].x<punt_jos_stanga.x)
{
punt_jos_stanga.x = puncte[i].x;
indice = i;
}
}
swap(puncte[1],puncte[indice]);
}
int main()
{
citire();
init();
alg();
afisare();
}