Pagini recente » Cod sursa (job #1383946) | Cod sursa (job #3179640) | Cod sursa (job #2390945) | Cod sursa (job #1596972) | Cod sursa (job #1412944)
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <queue>
#include <iomanip>
using namespace std;
struct Pair{
double x, y;
}eta;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
vector < Pair > C;
vector <int> sol;
vector <int> S;
queue <int> Q;
int n, mini;
void citire()
{
eta.x = 2000000000;
Pair p;
f>>n;
for(int i=0; i<n; i++){
f>>p.x>>p.y;
C.push_back(p);
if(p.x < eta.x || (p.x == eta.x && p.y < eta.y)){
eta = p;
mini = i;
}
}
C[mini] = C[0];
C[0] = eta;
}
int mycomp(Pair p1, Pair p2)
{
double tg1, tg2;
tg1 = (p1.y - eta.y) / (p1.x - eta.x);
tg2 = (p2.y - eta.y) / (p2.x - eta.x);
return tg1 < tg2;
}
void precalc()
{
sort(C.begin() + 1, C.end(), mycomp);
}
double arie(Pair p1, Pair p2, Pair p3)
{
double ar = 0;
ar += (p1.x*p2.y + p2.x*p3.y + p1.y*p3.x) - (p3.x*p2.y + p1.x*p3.y + p1.y*p2.x);
if(ar>0)
return 1;
return 0;
}
void rez()
{
int i=2;
S.push_back(0); S.push_back(1);
while(S.size() >= 2 && i<n){
for(; i<n && arie(C[S[S.size() - 2]], C[S.back()], C[i]); i++)
S.push_back(i);
if(i<n)
S.pop_back();
}
if(S.size() > 2){
g<<S.size()<<"\n";
for(i=0; i<S.size(); i++){
g<<fixed<<setprecision(6)<<C[S[i]].x<<" "<<C[S[i]].y<<"\n";
}
}
}
int main()
{
citire();
precalc();
rez();
return 0;
}