Pagini recente » Cod sursa (job #1460567) | Cod sursa (job #2229547) | Cod sursa (job #245488) | Cod sursa (job #374120) | Cod sursa (job #1221687)
#include<fstream>
#include<vector>
#include<utility>
#include<algorithm>
#define INF 999999999
using namespace std;
pair<double, double> v0, aux;
int n, i, poz, k;
double x, y;
int det(pair<double, double> v1, pair<double, double>v2, pair<double, double>v3){
return (v2.first-v1.first)*(v3.second-v1.second)-(v3.first-v1.first)*(v2.second-v1.second);
}
int cmp(pair<double, double>v1, pair<double, double>v2){
return det(v0, v1, v2)>0;
}
vector<pair <double, double> > v;
pair<double, double> s[120007];
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int main(){
in>>n;
v0.first=INF;
for(i=1; i<=n; i++){
in>>x>>y;
v.push_back(make_pair(x, y));
if(v[i-1]<v0){
v0=v[i-1];
poz=i-1;
}
}
aux=v[poz];
v[poz]=v[0];
v[0]=aux;
sort(v.begin()+1, v.end(), cmp);
s[0]=v[0];
s[1]=v[1];
k=1;
for(i=2; i<n; i++){
while(det(s[k-1], s[k], v[i])<=0 && k>=1){
k--;
}
s[++k]=v[i];
}
out<<k+1<<"\n";
for(i=0; i<=k; i++)
out<<s[i].first<<" "<<s[i].second<<"\n";
//for(i=0; i<v.size(); i++)
//out<<v[i].first<<" "<<v[i].second<<"\n";
return 0;
}