Cod sursa(job #1295976)

Utilizator stefanzzzStefan Popa stefanzzz Data 20 decembrie 2014 14:48:50
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.34 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
#define MAXN 100005
#define INF 2000000000
#define DINF 1e+300
using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");

int n, pol_size, l, r, u, d, maxl;
double area, min_area = DINF;
pair<int, int> v[MAXN];
vector< pair<int, int> > pol;

void infasuratoare();
inline long long det(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3);
inline double dist(pair<int, int> p1, pair<int, int> p2);

inline long long dotProduct_4P(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4);
inline long long crossProduct_4P(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4);
inline long long dotProduct_2P(pair<int, int> p1, pair<int, int> p2);
inline long long crossProduct_2P(pair<int, int> p1, pair<int, int> p2);

void get_dreapta(pair<int, int> p1, pair<int, int> p2, long long &a, long long &b, long long &c){
	a = p1.second - p2.second;
	b = p2.first - p1.first;
	c = 1LL * p1.first * p2.second - 1LL * p1.second * p2.first;
}

inline double dist(pair<int, int> p, long long &a, long long &b, long long &c){
	return fabs(a * p.first + b * p.second + c) / sqrt(a * a + b * b);
}

bool Comp(pair<int, int> p1, pair<int, int> p2){
	return det(v[1], p1, p2) > 0;
}

int main(){
	int i;
	long long a, b, c;

	f >> n;
	for(i = 1; i <= n; i++)
		f >> v[i].first >> v[i].second;

	infasuratoare();
	/*for(i = 0; i < pol_size; i++)
		g << pol[i].first << ' ' << pol[i].second << '\n';*/

	for(d = 0; dotProduct_4P(pol[l], pol[l + 1], pol[d], pol[d + 1]) >= 0; d++);
	for(r = d; crossProduct_4P(pol[l], pol[l + 1], pol[r], pol[r + 1]) >= 0; r++);
	for(u = r; dotProduct_4P(pol[l], pol[l + 1], pol[u], pol[u + 1]) <= 0; u++);

	for(l = 0; l < pol_size; l++){
		for(d; dotProduct_4P(pol[l], pol[l + 1], pol[d], pol[d + 1]) >= 0; d++);
		for(r; crossProduct_4P(pol[l], pol[l + 1], pol[r], pol[r + 1]) >= 0; r++);
		for(u; dotProduct_4P(pol[l], pol[l + 1], pol[u], pol[u + 1]) <= 0; u++);

		get_dreapta(pol[l], pol[l + 1], a, b, c);
		area = dist(pol[r], a, b, c);
		//cauta dreapta perpendiculara pe [l, l + 1] care trece prin u
		swap(a, b); //cauta dreapta perpendiculara pe [l, l + 1], care trece prin u
		b = -b;
		c = -a * pol[u].first - b * pol[u].second;
		area *= dist(pol[d], a, b, c);
		//g << l << ' ' << d << ' ' << r << ' ' << u << ' ' << area << '\n';
		if(area < min_area) min_area = area;
	}	
			
	g << fixed << setprecision(2) << min_area << '\n';
	 
	f.close();
	g.close();
	return 0;
}

void infasuratoare(){
	int i, left = 1;
	
	for(i = 2; i <= n; i++)
		if(v[i].first < v[left].first || (v[i].first == v[left].first && v[i].second < v[left].second)) left = i;

	swap(v[1], v[left]);
	sort(v + 2, v + n + 1, Comp);
	pol.push_back(v[1]);

	for(i = 2; i <= n; i++){
		while(pol.size() >= 2 && (det(pol[pol.size() - 2], pol[pol.size() - 1], v[i]) < 0)) pol.pop_back();
		if(pol.size() >= 2 && det(pol[pol.size() - 2], pol[pol.size() - 1], v[i]) == 0 && dist(pol[pol.size() - 2], pol[pol.size() - 1]) > dist(pol[pol.size() - 2], v[i]))
			continue;
		pol.push_back(v[i]);
	}

	pol_size = pol.size();
	for(i = 0; i < pol_size + 10; i++)
		pol.push_back(pol[i]);
}

inline long long det(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3){
	// | x1 y1 1 |
	// | x2 y2 1 |
	// | x3 y3 1 |

	return 1LL * p1.first * (p2.second - p3.second) - 1LL * p1.second * (p2.first - p3.first) + 1LL * p2.first * p3.second - 1LL * p2.second * p3.first;
}

inline double dist(pair<int, int> p1, pair<int, int> p2){
	int dx = p1.first - p2.first, dy = p1.second - p2.second;
	return sqrt(1LL * dx * dx + 1LL * dy * dy);
}

inline long long dotProduct_4P(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4){
	return dotProduct_2P(make_pair(p2.first - p1.first, p2.second - p1.second), make_pair(p4.first - p3.first, p4.second - p3.second));
}
inline long long crossProduct_4P(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4){
	return crossProduct_2P(make_pair(p2.first - p1.first, p2.second - p1.second), make_pair(p4.first - p3.first, p4.second - p3.second));
}
inline long long dotProduct_2P(pair<int, int> p1, pair<int, int> p2){
	return 1LL * p1.first * p2.first + 1LL * p1.second * p2.second;
}
inline long long crossProduct_2P(pair<int, int> p1, pair<int, int> p2){
	return 1LL * p1.first * p2.second - 1LL * p1.second * p2.first;
}