Pagini recente » Cod sursa (job #3360779) | Cod sursa (job #3360863) | Cod sursa (job #3360778) | Cod sursa (job #3360799) | Cod sursa (job #3359393)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct{
double x,y;
};
Punct Prim;
double det(Punct A, Punct B, Punct C){
return B.x*C.y + A.x*B.y + A.y*C.x - A.y*B.x - B.y*C.x - A.x*C.y;
}
double dist(Punct A,Punct B){
return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
bool comp(Punct A,Punct B){
double determinant = det(A,B,Prim);
if(determinant != 0){
return determinant>0;
}
return dist(Prim,A) < dist(Prim,B);
}
int main(){
int n;
fin>>n;
vector<Punct> p(n);
int prim=0;
for(int i=0;i<n;i++){
fin>>p[i].x>>p[i].y;
if(p[i].y<p[prim].y || (p[i].y == p[prim].y && p[i].x >= p[prim].x)){
prim=i;
}
}
swap(p[0],p[prim]);
Prim = p[0];
sort(p.begin()+1,p.end(),comp);
vector<Punct> inconjor;
inconjor.push_back(p[0]);
inconjor.push_back(p[1]);
for(int i=2;i<n;i++){
Punct penultim = inconjor[inconjor.size()-2], ultim = inconjor[inconjor.size()-1], curent=p[i];
while(inconjor.size()>=2 && det(penultim,ultim,curent)<=0){
inconjor.pop_back();
if(inconjor.size()>=2)
penultim = inconjor[inconjor.size()-2], ultim = inconjor[inconjor.size()-1], curent=p[i];
}
inconjor.push_back(curent);
}
fout<<inconjor.size()<< '\n';
for(size_t i=0;i<inconjor.size();i++){
fout<<fixed<<setprecision(6)<<inconjor[i].x<< " "<<inconjor[i].y<< '\n';
}
fin.close();
fout.close();
return 0;
}