Pagini recente » Cod sursa (job #1582257) | Cod sursa (job #2837511) | Cod sursa (job #1207826) | Cod sursa (job #1205433) | Cod sursa (job #800805)
Cod sursa(job #800805)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define nmax 120005
#define Eps 0.000000000001
#define ll long long
#define inf (1<<29)
int n, poz;
pair<double, double> pct_init, v[nmax];
vector<int> puncte, a;
double modul(double X ){
if (X < 0.000000000000){
X = X * -1.00000000000;
}
return X;
}
bool cmp(int i, int j){
//am punctele i, si j, si pct_initial(ala initial)
//primul e mai "mic" fata de al doilea daca ( (x1 - X) / (y1-Y) ) < ( (x2 - X) / (y2 - Y) ); => pt a evita impartirea
// = > (x1 - x) * (y2 - y) < (y1 - y) * (x2 - x);
int x1 = v[i].first; int y1 = v[i].second;
int x2 = v[j].first; int y2 = v[j].second;
int X = pct_init.first; int Y = pct_init.second;
if ( (x1-X) * (y2-Y) > (y1 - Y) * (x2 - X) ) return 1;
return 0;
}
void citeste(){
f >> n;
pct_init = make_pair(inf, inf);
for(int i=1; i<=n; ++i){
double x, y;
f >> x >> y;
v[i] = make_pair(x, y);
if (x < pct_init.first){
pct_init = make_pair(x, y);
poz = i;
}
else if ( modul( x - pct_init.first ) <= Eps ){//daca x-ul e egal; ma uit la y(imi trebuie cel mai din stanga si cel mai de jos
if (y < pct_init.second){
pct_init = make_pair(x, y);
poz = i;
}
}
}
//le sortez pe celelalte in functie de punctul initial;
for(int i=1; i<=n; ++i){
if (i == poz) continue;//daca e punctul ala initial nu il mai sortez
puncte.push_back( i );//bag doar pozitiile in vectorul initial;
}
sort(puncte.begin(), puncte.end(), cmp);
}
double semn( int i, int j, int k ){
double x1 = v[i].first; double y1 = v[i].second;
double x2 = v[j].first; double y2 = v[j].second;
double x3 = v[k].first; double y3 = v[k].second;
//acum aflu determinantul lui :
//x1 y1 1
//x2 y2 1
//x3 y3 1
//daca il explicitez o sa am x1*(y2-y3) + y1*(x3-x2) + x2*y3 - x3 * y2;
double c = x2*y3 - x3*y2;
return ( x1*(y2-y3) + y1*(x3-x2) + c );
}
void rezolva(){
//fac cu scanarea graham; imi aleg cel mai din sanga jos puncte dintre cele n (asta sigur face parte din infasuratoare) apoi le sortez pe restul
//in functie de panta fata de acest punct ales;
// apoi incep ce iau punctele sortate si ma tot uit sa vad ce devierie se produc la introducerea fiecarui punct in infasuratoare
//le am sortate si incep scanarea; //tin o stiva pt ca eu tot timpul trebuie sa ma uit la ultimul introdus (evident la ala dinaintea astuia pe care il bag acum)
//bag pct initial
a.push_back( poz );//bag pozitia in vectorul initial a punctului initial ales
a.push_back( puncte[0] );//il bag si pe aldoilea; ca eu am nevoie de minim 3 tot timpul
for(int i=1; i<puncte.size(); ++i){
//cout << puncte[i] << "\n";
//iau punctul asta si vad cate pot scoate; pp ca asta face parte din infasuratoare
//acum scot toate punctele care sunt in interior; asta o fac cu determinant ; le scot si pe alea care sunt coliniare
int ultim = a.size() - 1;// imi indica la ultimul punct bagat
//cout << a[ultim-1] << " " << a[ultim] << " " << puncte[i] << "\n";
while( a.size() >= 2 && semn( a[ultim-1], a[ultim], puncte[i] ) > 0.0000000 ){
//ultimul punct il scot daca se afla in semiplanul din stanga a dreptei formate de pct-le a[ultim-1], puncte[i])
//adica e in interior
a.pop_back();
--ultim;
}
a.push_back( puncte[i] );
}
g << a.size() << "\n";
g << fixed;
for(int i=a.size()-1; i>=0; --i){
g << setprecision(12) << v[ a[i] ].first << " " << setprecision(12)<< v[ a[i] ].second << "\n";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}