Pagini recente » Cod sursa (job #2870028) | Cod sursa (job #2468196) | Cod sursa (job #2287851) | Cod sursa (job #2401916) | Cod sursa (job #2659617)
#define NMAX 120005
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{
double x, y;
}P[NMAX];
vector <punct> V1, V2;
int n;
double orientare(punct A, punct B, punct C){
return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
bool compare(punct P0, punct P1){
if(P0.x < P1.x)
return 1;
else if(P0.x == P1.x && P0.y < P1.y)
return 1;
return 0;
}
void citire(){
f>>n;
for(int i=0; i<n; i++)
f>>P[i].x>>P[i].y;
sort(P, P+n, compare);
}
void afisare(){
g<<V1.size() + V2.size() - 2<<'\n';
for(int i=0; i<V1.size()-1; i++)
g<<fixed<<setprecision(6)<<V1[i].x<<" "<<V1[i].y<<'\n';
for(int i=0; i<V2.size()-1; i++)
g<<fixed<<setprecision(6)<<V2[i].x<<" "<<V2[i].y<<'\n';
}
void solve(){
V1.push_back(P[0]);
for(int i=1; i<n; i++){
while(V1.size() > 1 && orientare(V1[V1.size()-2], V1[V1.size()-1], P[i]) < 0)
V1.pop_back();
V1.push_back(P[i]);
}
V2.push_back(P[n-1]);
for(int i=n-2; i>=0; i--){
while(V2.size() > 1 && orientare(V2[V2.size()-2], V2[V2.size()-1], P[i]) < 0)
V2.pop_back();
V2.push_back(P[i]);
}
}
int main()
{
citire();
solve();
afisare();
return 0;
}