Cod sursa(job #1555831)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 23 decembrie 2015 17:06:35
Problema Regiuni Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;

constexpr int maxn = 1010;

struct dreapta{
	int a, b, c; };

struct punct{
	int x, y; };

int calc(const dreapta d, const punct p){
	return d.a * p.x + d.b * p.y + d.c; }

int main(){
	ifstream f("regiuni.in");
	ofstream g("regiuni.out");

	int n, m;
	f >> n >> m;

	static vector<dreapta> drepte(n);
	static vector<punct> puncte(m);

	for(auto& d : drepte){
		f >> d.a >> d.b >> d.c; }
	for(auto& p : puncte){
		f >> p.x >> p.y; }

	static vector<bitset<maxn>> car(m, 0);

	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			car[j][i] = (calc(drepte[i], puncte[j]) > 0); } }

	for(int i = maxn-1; i >= 0; --i){
		partition(begin(car), end(car), [i](const bitset<maxn>& b){
			return b[i]; }); }

	int rez = 1, model = 0;
	for(int i = 1; i < m; ++i){
		if(car[model] != car[i]){
			++rez;
			model = i; } }

	g << rez;
	return 0; }