Submission #75208562

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
struct monsutaa_s {
  int id, X, Y;
};
/*
角度が違う → ±2
角度は同じなのでID順 → ±1
*/
int cmp(const void* x, const void* y) {
  struct monsutaa_s a = *(const struct monsutaa_s*)x, b = *(const struct monsutaa_s*)y;
  long long judge;
  if (a.Y <= 0 && b.Y > 0) return -2;
  if (a.Y > 0 && b.Y <= 0) return 2;
  if (a.Y == 0 && b.Y == 0) {
    if (a.X > 0 && b.X < 0) return -2;
    if (a.X < 0 && b.X > 0) return 2;
  }
  judge = (long long)a.X * b.Y - (long long)b.X * a.Y;
  if (judge != 0) return ((judge > 0) - (judge < 0)) * 2;
  return (a.id > b.id) - (a.id < b.id);
}
int N, Q;
struct monsutaa_s ms[212345];
int A[212345], B[212345];
int same_left[212345], same_right[212345];
int id_to_pos[212345];
int main(void) {
  int i;
  if (scanf("%d%d", &N, &Q) != 2) return 1;
  for (i = 0; i < N; i++) {
    if (scanf("%d%d", &ms[i].X, &ms[i].Y) != 2) return 1;
    ms[i].id = i + 1;
  }
  for (i = 0; i < Q; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct monsutaa_s {
	int id, X, Y;
};

/*
角度が違う → ±2
角度は同じなのでID順 → ±1
*/
int cmp(const void* x, const void* y) {
	struct monsutaa_s a = *(const struct monsutaa_s*)x, b = *(const struct monsutaa_s*)y;
	long long judge;
	if (a.Y <= 0 && b.Y > 0) return -2;
	if (a.Y > 0 && b.Y <= 0) return 2;
	if (a.Y == 0 && b.Y == 0) {
		if (a.X > 0 && b.X < 0) return -2;
		if (a.X < 0 && b.X > 0) return 2;
	}
	judge = (long long)a.X * b.Y - (long long)b.X * a.Y;
	if (judge != 0) return ((judge > 0) - (judge < 0)) * 2;
	return (a.id > b.id) - (a.id < b.id);
}

int N, Q;
struct monsutaa_s ms[212345];
int A[212345], B[212345];

int same_left[212345], same_right[212345];

int id_to_pos[212345];

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &ms[i].X, &ms[i].Y) != 2) return 1;
		ms[i].id = i + 1;
	}
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &A[i], &B[i]) != 2) return 1;
	}
	qsort(ms, N, sizeof(*ms), cmp);
	for (i = 0; i < N; i++) {
		id_to_pos[ms[i].id] = i;
	}
	same_left[0] = 0;
	for (i = 1; i < N; i++) {
		same_left[i] = cmp(&ms[i - 1], &ms[i]) / 2 == 0 ? same_left[i - 1] : i;
	}
	same_right[N - 1] = N - 1;
	for (i = N - 2; i >= 0; i--) {
		same_right[i] = cmp(&ms[i], &ms[i + 1]) / 2 == 0 ? same_right[i + 1] : i;
	}
	for (i = 0; i < Q; i++) {
		int apos = id_to_pos[A[i]], bpos = id_to_pos[B[i]];
		int aid = same_left[apos], bid = same_right[bpos];
		if (cmp(&ms[apos], &ms[bpos]) / 2 <= 0) {
			printf("%d\n", bid - aid + 1);
		} else {
			printf("%d\n", (N - aid) + (bid + 1));
		}
	}
	return 0;
}

/*

とりあえず原点からX軸の正の方向に向かう線を基準とし、ソート
外積っぽい何かで大小関係を判定できるはず

o--> (x1, y1) = (1, 0)
|
v (x2, y2) = (0, -1)

x1*y2 - x2*y1 = -1 - 0 = -1
このとき、(x1, y1) のほうが前

*/

Submission Info

Judge Result