Cod sursa(job #409683)

Utilizator AstronothingIulia Comsa Astronothing Data 3 martie 2010 19:58:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdio>

using namespace std;

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

bool cmp(point a,point b) {
	return a.u < b.u || (a.u == b.u && a.x < b.x);
}

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()
{
	FILE* f = fopen("infasuratoare.in","r");
	FILE* f2 = fopen("infasuratoare.out","w");
	int N;
	fscanf(f,"%d",&N);
	vector<point> p;
	for(int i=0;i<N; ++i)
	{
		point pp;
		fscanf(f,"%lf %lf",&(pp.x),&(pp.y));
		printf("%.6lf\n",pp.x);
		p.push_back(pp);
	}

    point pRef;
    pRef.x = 10;
    pRef.y = 0;
	vector<point> st;
	for(int i=0; i<N; i++)
	{
		p[i].u = atan2((p[i].y - pRef.y),(p[i].x - pRef.x));
	}
	sort(p.begin(), p.end(), cmp);

	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;
		}
	}

	st.push_back(p[indmin]);
	st.push_back(p[(indmin+1)%N]);
	int i=(indmin+2)%N;
	int T = i-1>0 ? i-1 : N-1;
	while(i!=T)
	{
	    if(i>(indmin+1)%N) T = (indmin+1)%N;
	    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; }
	}
	fprintf(f2,"%d\n",st.size()-1);
	for(int i=1; i<st.size(); ++i)
	{
	    fprintf(f2,"%.6lf %.6lf\n",st[i].x,st[i].y);
	}
	return 0;
}