// begin compatibility layer v2: syzoj2 interaction interface to testlib.h
#define main(...) __menci_main_compatibility__(int argc, char *argv[])
#include <testlib.h>
// end compatibility layer v2: syzoj2 interaction interface to testlib.h

#include <bits/stdc++.h>

#define sz(x) ((int)(x).size())

using namespace std;

typedef long long ll;

struct Vec2
{
	ll x, y;

	Vec2() {}
	Vec2(ll nx, ll ny) : x(nx), y(ny) {}

	Vec2 operator + (const Vec2 & b) const { return { x+b.x, y+b.y }; }
	Vec2 operator - (const Vec2 & b) const { return { x-b.x, y-b.y }; }
	Vec2 operator - () const { return { -x, -y }; }
	Vec2 operator * (ll b) const { return { x*b, y*b }; }

	Vec2 & operator += (const Vec2 & b) { x+=b.x; y+=b.y; return *this; }
	Vec2 & operator -= (const Vec2 & b) { x-=b.x; y-=b.y; return *this; }
	Vec2 & operator *= (ll b) { x*=b; y*=b; return *this; }

	bool operator == (const Vec2 & b) const { return x==b.x && y==b.y; }
	bool operator != (const Vec2 & b) const { return x!=b.x && y!=b.y; }
	bool operator <  (const Vec2 & b) const { return x==b.x ? y<b.y : x<b.x; }
	bool operator <= (const Vec2 & b) const { return x==b.x ? y<=b.y : x<b.x; }
	bool operator >  (const Vec2 & b) const { return x==b.x ? y>b.y : x>b.x; }
	bool operator >= (const Vec2 & b) const { return x==b.x ? y>=b.y : x>b.x; }
};

Vec2 operator * (ll b, const Vec2 & a) { return { b*a.x, b*a.y }; }
ll dot(const Vec2 & a, const Vec2 & b) { return a.x*b.x + a.y*b.y; }
ll cross(const Vec2 & a, const Vec2 & b) { return a.x*b.y - a.y*b.x; }
ll length2(const Vec2 & a) { return a.x*a.x + a.y*a.y; }

int n;
vector < Vec2 > p;
Vec2 w;
int qlim, qwas;
vector<int> used;

FILE * in;

vector < int > readPolygon()
{
	int k, x;scanf("%d",&k);
	if (k<3||k>n)
	{
		freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
		fprintf(stderr, "the number of points of the polygon %d out of range.", k);
		exit(0);
	}
	vector < int > pol;
	for (int i = 0; i < k; ++i)
	{
		scanf("%d",&x);
		if (x<1||x>n)
		{
			freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
			fprintf(stderr, "the %d-th point out of range.", x);
			exit(0);
		}
		pol.push_back(x - 1);
	}

	if (cross(p[pol[1]] - p[pol[0]], p[pol[2]] - p[pol[0]]) < 0)
		reverse(pol.begin(), pol.end());
	for (int i = 0; i < k; ++i) {
		if (used[pol[i]]++) {
			freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
			fprintf(stderr, "same point twice in polygon");
			exit(0);
		}
	}
	for (int i = 0; i < k; ++i) --used[pol[i]];
	int pos = 0;
	for (int i = 0; i < k; i++) {
		if (p[pol[i]] < p[pol[pos]]) {
			pos = i;
		}
	}
	Vec2 p0 = p[pol[pos]];
	for (int i = 0; i < k; ++i)
	{
		Vec2 p1 = p[pol[(i + pos) % k]];
		Vec2 p2 = p[pol[(i + pos + 1) % k]];
		Vec2 p3 = p[pol[(i + pos + 2) % k]];
		if (cross(p2 - p1, p3 - p1) <= 0 || cross(p2 - p0, p3 - p0) < 0) {
			freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
			fprintf(stderr, "polygon should be convex");
			exit(0);
		}
	}

	return pol;
}

bool inAngle(Vec2 p0, Vec2 p1, Vec2 p2, Vec2 w)
{
	p1 -= p0;
	p2 -= p0;
	w -= p0;
	return cross(p1, w) >= 0 && cross(w, p2) >= 0;
}

bool inPolygon(const vector < int > & pol, Vec2 w)
{
	int k = sz(pol);
	Vec2 p0 = p[pol[0]];
	if (!inAngle(p0, p[pol[1]], p[pol[k - 1]], w))
		return false;
	int l = 1, r = k - 1;
	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		if (inAngle(p0, p[pol[1]], p[pol[mid]], w))
			r = mid;
		else
			l = mid;
	}
	return inAngle(p[pol[l]], p[pol[r]], p0, w);
}

int main(int argc, char * argv[])
{
	in = fopen("input", "r");
	fscanf(in, "%d%d", &n, &qlim);
	p.resize(n);
	used.assign(n, 0);
	for (int i = 0; i < n; ++i)
		fscanf(in, "%lld %lld", &p[i].x, &p[i].y);
	int q;fscanf(in, "%d", &q);
	printf("%d\n", n);
	for (Vec2 a : p)
		printf("%lld %lld\n", a.x, a.y);
	printf("%d\n", q);
	fflush(stdout);

	int sum_q = 0, max_q = 0;
	for (int ii = 0; ii < q; ++ii)
	{
		fscanf(in, "%lld%lld", &w.x, &w.y);
		w.y -= w.x;
		w.x ^= (unsigned)(ii + 1) * 239;
		qwas = 0;
		while (true)
		{
			char s[3];scanf("%s",s);
			if (s[0] == '?' && strlen(s) == 1)
			{
				if (++qwas > qlim)
				{
					freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
					fprintf(stderr, "test #%d: cotestant used more than %d queries", ii + 1, qlim);
					return 0;
				}
				vector < int > pol = readPolygon();
				
				if (inPolygon(pol, w))
					printf("Yes\n");
				else
					printf("No\n");
				fflush(stdout);
			}
			else if (s[0] == '!' && strlen(s) == 1)
			{
				//fprintf(stderr, "THE ANSWER\n");
				vector < int > pol = readPolygon();
				/*
				tout << sz(pol) << "\n";
				for (int x : pol)
					tout << x + 1 << " ";
				tout << "\n";*/
				if (!inPolygon(pol, w))
				{
					freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
					fprintf(stderr, "test #%d: point is outside the polygon", ii + 1);
					return 0;
				}
				vector < bool > vs(n, false);
				for (int x : pol)
					vs[x] = true;
				for (int i = 0; i < n; ++i)
					if (!vs[i] && inPolygon(pol, p[i])) {
						freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
						fprintf(stderr, "test #%d: polygon contains given points", ii + 1);
						return 0;
					}
				break;
			} else {
				freopen("score.txt", "w", stdout);puts("0");fclose(stdout);fclose(in);
				fprintf(stderr, "test #%d: incorrect query %s", ii + 1, s);
				return 0;
			}
		}
		//fprintf(stderr, "%d of %d queries\n", qwas, qlim);
		sum_q += qwas;
		max_q = max(max_q, qwas);
	}
	//tout << format("%d tests, n=%d, average %.3f queries per test, max = %d queries", q, n, 1. * sum_q / q, max_q) << endl;
	freopen("score.txt", "w", stdout);puts("100");fclose(stdout);fclose(in);
	fprintf(stderr, "%d tests, n=%d, average %.3f queries per test, max = %d queries", q, n, 1. * sum_q / q, max_q);
	return 0;
}

// begin compatibility layer v2: syzoj2 interaction interface to testlib.h
#undef main

std::string __menci_read_file_content(const char *filename) {
	FILE *file = fopen(filename, "r");
	(void)fseek(file, 0, SEEK_END);
	size_t length = ftell(file);
	rewind(file);
	std::string content(length, ' ');
	(void)fread((void *)content.data(), 1, length, file);
    while (content.length() > 0 && content.back() == '\n') content.pop_back();
	return content;
}

int stderr_bak;

int main(int argc, char *argv[]) {
	registerInteraction(argc, argv);
	(void)symlink(argv[1], "input");
	(void)symlink(argv[2], "answer");
	// backup stderr
	stderr_bak = dup(STDERR_FILENO);
	(void)freopen("__message", "w", stderr);

    void __menci_exit();
    atexit(__menci_exit);

	(void)__menci_main_compatibility__(argc, argv);
}

void __menci_exit() {
    fflush(NULL);

    // restore stderr
	(void)dup2(stderr_bak, STDERR_FILENO);

	std::string message = __menci_read_file_content("__message");
	std::string score = __menci_read_file_content("score.txt");
	if (score.empty() || score == "0")
		quit(_wa, message);
	else if (score == "100")
		quit(_ok, message);
	else
		quitp(std::stod(score), "%s", message.c_str());
}
// end compatibility layer v2: syzoj2 interaction interface to testlib.h

来源：LOJ