Cod sursa(job #2224828)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 25 iulie 2018 11:56:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
#include<vector>
#include<utility>
#include<algorithm>
#include<iomanip>
using namespace std;

vector< pair<double, double> > a, st;
int n, inf=2000000000;
double xr, yr;

double det(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3) {
	return p1.first*p2.second + p2.first*p3.second + p1.second*p3.first - p3.first*p2.second - p3.second*p1.first - p2.first*p1.second;	
}

double polar(pair<double, double> p) {
  double xc = p.first;
  double yc = p.second;	
	
  if (xc==xr && yc<yr) return -inf;
  else if (xc==xr && yc>yr) return inf;
  else if (xc==xr && yc==yr) return -inf-1;
  else return (yc-yr)/(xc-xr);
}

bool cmp(pair<double, double> p1, pair<double, double> p2) {
	return polar(p1)<polar(p2);	
}

int main(void) {
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	
	cin>>n; xr=2000000000;
	for (int i=1; i<=n; ++i){
	  double x, y; cin>>x>>y;
	  if (x<xr) { xr=x; yr=y; }
	  else if (x==xr && y<yr) yr=y;
	  a.push_back(make_pair(x,y));	
	}
	
	sort(a.begin(), a.end(), cmp);
	
	st.push_back(a[0]);
	st.push_back(a[1]);
	
	for (int i=2; i<a.size(); ++i) {
	   
	    while (st.size()>1 && det(st[st.size()-2], st[st.size()-1], a[i])<0) { auto it=st.end(); --it; st.erase(it); }
		st.push_back(a[i]);	
		
	}
	
	cout<<st.size()<<"\n";
	
	for (int i=0; i<st.size(); ++i) cout<<setprecision(10)<<fixed<<st[i].first<<" "<<st[i].second<<"\n";
	
	return 0;
}