Cod sursa(job #292178)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 30 martie 2009 20:41:33
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN  "infasuratoare.in"
#define OUT "infasuratoare.out"
#define N_MAX 1<<17

typedef vector<int> VI;
typedef pair<db,db> pi;
typedef vector<string> VS;

int N,last;
vector<pi> V,S(N_MAX); 
vector< pair<db,int> > A;

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	
	scanf("%d\n",&N);
	
	V.resize(N+1);
	FOR(i,1,N)
		scanf("%lf %lf\n",&V[i].f,&V[i].s);
}

II db semn(pi i1,pi i2,pi i3)  
{  
    return (db) i1.f * i2.s + i2.f * i3.s + i3.f * i1.s - i1.s * i2.f - i2.s * i3.f - i3.s * i1.f;  
}  

II void solve()
{
	db x1,y1;
	
	FOR(i,1,N)
		if(V[i].s < y1 || (V[i].s == y1 && V[i].f < x1) )
			y1 = V[i].s,x1 = V[i].f;
	
	S[++last] = mp(x1,y1);
	
	FOR(i,1,N)
		if(V[i].f > x1)
			A.pb( mp(V[i].s  - y1 / V[i].f - x1,i) );
	sort(A.begin(),A.end() );
	
	S[++last] = V[ A[0].s ];
	FOR(i,1,(int)A.sz()-1)
	{
		for(;last >= 2 && semn(S[last-1],S[last],V[ A[i].s ]) < 0;--last);
		S[++last] = V[ A[i].s ];
	}
	
	A.resize(0);
	FOR(i,1,N)
		if(V[i].f <= x1 && V[i] != mp(x1,y1))
			A.pb( mp(y1 - V[i].s / x1 - V[i].f,i) );
	sort(A.begin(),A.end() );
	
	FOR(i,0,(int)A.sz()-1)
	{
		for(;last >= 2 && semn(S[last-1],S[last],V[ A[i].s ]) < 0;--last);
		S[++last] = V[ A[i].s ] ;
	}
	
	printf("%d\n",last);
	FOR(i,1,last)
		printf("%lf %lf\n",S[i].f,S[i].s);
 }

int main()
{
	scan();
	solve();
	return 0;
}