HDU4380 / Farmer Greedy

Posted on By 二价氢

题目:HDU 4380

给你若干(\(\le 100\)个)A类点和若干(\(\le 1000\)个)B类点,问你有多少个A类点围成的三角形含奇数个B类点

首先,我们可以预先处理出有每条线段上方有多少个\(A\)类点,然后再处理枚举点\((i,j,k)\),则可以在\(O(1)\)时间内计算有多少个\(B\)类点在这个三角形当中。

速度很快,使用long long计算,速度为HDU上的RANK 2

AC-Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

#define x first
#define y second

typedef pair<int , int> pii;
const int maxn = 100 + 5;
const int maxm = 1000 + 5;

int upper[maxn][maxn];
pii gold_mine[maxm];
pii farmer_house[maxn];
int n , m , caseno;

bool above_line(const pii &a , const pii &b , const pii &c)
	// return if c is above the line a-b
{
	long long x1 = b.x - a.x;
	long long x2 = c.x - a.x;
	long long y1 = b.y - a.y;
	long long y2 = c.y - a.y;
	return (x1 * y2) - (x2 * y1) > 0;
}

int eabs(int a)
{
	return (a < 0) ? -a : a;
}

void work()
{
	int tx , ty;
	for (int i = 0 ; i < n ; i++)
	{
		scanf("%d%d" , &tx , &ty);
		farmer_house[i] = pii(tx , ty);
	}
	for (int i = 0 ; i < m ; i++)
	{
		scanf("%d%d" , &tx , &ty);
		gold_mine[i] = pii(tx , ty);
	}
	sort(&farmer_house[0] , &farmer_house[n]);
	sort(&gold_mine[0] , &gold_mine[m]);
	memset(upper , 0 , sizeof(upper));
	int beg = 0;
	for (int i = 0 ; i < n ; i++)
	{
		while (gold_mine[beg].x < farmer_house[i].x)
			beg++;
		for (int j = i + 1 ; j < n ; j++)
		{
			if (farmer_house[j].x == farmer_house[i].x)
				continue;
			for (int k = beg ; k < m && gold_mine[k].x < farmer_house[j].x ; k++)
				upper[i][j] += above_line(farmer_house[i] , farmer_house[j] , gold_mine[k]);
			upper[j][i] = upper[i][j];
			//fprintf(stderr , "%d %d - %d %d (cnt = %d)\n" , farmer_house[i].x , farmer_house[i].y , farmer_house[j].x , farmer_house[j].y , upper[i][j]);
		}
	}

	int ans = 0;

	for (int i = 0 ; i < n ; i++)
		for (int j = i + 1 ; j < n ; j++)
			for (int k = j + 1 ; k < n ; k++)
				ans += abs(upper[i][j] + upper[j][k] - upper[k][i]) % 2;
	printf("Case %d: %d\n" , ++caseno , ans);
}

int main()
{
	while (~scanf("%d%d" , &n , &m))
		work();
}