Cod sursa(job #408008)

Utilizator AstronothingIulia Comsa Astronothing Data 2 martie 2010 19:48:01
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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;
}

double dist(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

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;
	if(det == 0 && dist(a,c)>dist(a,b)) return 0;
	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;
	int T = 1;
	while(i!=T)
	{
	    if(i>2) T = 2;
	    i = i%N;
        if(st.size()<2) { st.push_back(p[i]); continue; }

        int d = isleft(p[i],st[st.size()-1],st[st.size()-2]);
        if(d == 1) { st.push_back(p[i++]); continue; }
        if(d == 0) { st.pop_back(); continue; }

	}
	f2<<st.size()-2<<"\n";
	for(int i=2; i<st.size(); ++i) f2<<st[i].x<<" "<<st[i].y<<"\n";
	return 0;
}