pku1687.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 54 行

#include <stdio.h>
#include <string.h>
#define SIZE 60

typedef struct Point
{
	int x, y;
}Point;

Point p[SIZE];
int N;
int id[SIZE];

int abs(int X){return X > 0 ? X : -X;}

void solve()
{
	int i, k, j, m;
	int max, maxid, area;
	scanf("%d", &N);
	for (i = 1; i <= N; i++)
		scanf("%d %d", &p[i].x, &p[i].y);
	scanf("%d", &k);
	max = -1;
	maxid = -1;
	for (j = 1; j <= k; j++)
	{
		scanf("%d", &m);
		for (i = 0; i < m; i++)
			scanf("%d", &id[i]);
		area = 0;
		for (i = 0; i < m; i++)
		{
			area += p[id[i]].x * p[id[(i+1)%m]].y - p[id[i]].y * p[id[(i+1)%m]].x;
		}
		area = abs(area);
		if (area > max)
		{
			max = area;
			maxid = j;
		}
	}
	printf("%d\n", maxid);
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
		solve();
	return 0;
}