Cod sursa(job #406413)

Utilizator AstronothingIulia Comsa Astronothing Data 1 martie 2010 15:17:29
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct point{ double x,y; double u;};

bool cmp(point a,point b) {
	return a.u < b.u;
}

int isleft(point c, point b, point a)
{
	double det = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
	if(det>0) return 1;
	return 0;
}

int main()
{
	ifstream f("infasuratoare.in");
	ofstream f2("infasuratoare.out");
	int N;
	f>>N;
	vector<point> p;
	for(int i=0;i<N; ++i)
	{
		double x,y;
		f>>x>>y;
		point pp;
		pp.x = x;
		pp.y = y;
		p.push_back(pp);
	}

	int indmin = 0;
	for(int i=1;i<N;++i)
	{
		if((p[indmin].x<p[i].x) || (p[indmin].x==p[i].x && p[indmin].y>p[i].y))
		{
			indmin = i;
		}
	}
	
	vector<point> st;
	for(int i=0; i<N; i++) 
	{
		p[i].u = atan2((p[i].y - p[indmin].y),(p[i].x - p[indmin].x));
	}

	sort(p.begin(), p.end(), cmp);
	//for(int i=1; i<N; ++i) cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].u<<"\n";

	st.push_back(p[0]);
	st.push_back(p[1]);
	int i=2;
	while(i<N)
	{
		if(isleft(p[i],st[st.size()-1],st[st.size()-2]))
		{
			st.push_back(p[i]);
			++i;
		}
		else st.pop_back();
	}
	f2 << st.size() << endl;
	for(int i=0; i<st.size(); ++i) f2<<st[i].x<<" "<<st[i].y<<"\n";
	return 0;
}