Submission #69426542

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <limits.h>
#include <inttypes.h>
static unsigned int rx = 101280534u;
static unsigned int ry = 356793812u;
static unsigned int rz = 3171697253u;
static unsigned int rw = 732686597u;
unsigned int randint_raw(void) {
  unsigned int t;
  t = (rx ^ (rx << 11));
  rx = ry; ry = rz; rz = rw;
  rw = (rw ^ (rw >> 19)) ^ (t ^ (t >> 8));
  return rw;
}
/* [0, max) */
unsigned int randint(unsigned int max) {
  unsigned int d = ((UINT_MAX % max) + 1) % max;
  unsigned int sel;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <limits.h>
#include <inttypes.h>

static unsigned int rx = 101280534u;
static unsigned int ry = 356793812u;
static unsigned int rz = 3171697253u;
static unsigned int rw = 732686597u;

unsigned int randint_raw(void) {
	unsigned int t;
	t = (rx ^ (rx << 11));
	rx = ry; ry = rz; rz = rw;
	rw = (rw ^ (rw >> 19)) ^ (t ^ (t >> 8));
	return rw;
}

/* [0, max) */
unsigned int randint(unsigned int max) {
	unsigned int d = ((UINT_MAX % max) + 1) % max;
	unsigned int sel;
	do {
		sel = randint_raw();
	} while (sel > UINT_MAX - d);
	return sel % max;
}

int N;
int x[512345], y[512345];

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &x[i], &y[i]) != 2) return 1;
	}
	for (i = 0; i < 50; i++) {
		int j;
		int s1 = randint(N);
		int s2 = randint(N - 1);
		int64_t a, b, c;
		int cnt = 0;
		if (s2 >= s1) s2++;
		a = y[s2] - y[s1];
		b = x[s1] - x[s2];
		c = -(a * x[s1] + b * y[s1]);
		for (j = 0; j < N; j++) {
			cnt += a * x[j] + b * y[j] + c == 0;
		}
		if (cnt > N / 2) {
			puts("Yes");
			printf("%" PRId64 " %" PRId64 " %" PRId64 "\n", a, b, c);
			return 0;
		}
	}
	puts("No");
	return 0;
}

/*

異なる2点を選ぶ → それらを通る直線が決まる
過半数を通る直線が存在するならば、それらを選べれば勝ち
2点適当に選んでそれらが両方正解の確率は、だいたい1/2×1/2=1/4くらいのはず
よって、ミラー・ラビン法的に考えて、まあ50回くらいトライすればまずいけるやろ

(x1, y1) と (x2, y2) を通る直線は
傾き (y2 - y1) / (x2 - x1) なので y = (y2 - y1) / (x2 - x1) * x + k
変形して (y2 - y1) * x + (x1 - x2) * y + k * (x2 - x1) = 0

*/

Submission Info

Judge Result