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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <algorithm>
using namespace std;

int n,r,w,t;
struct car {
	int type; 
	int x;
	int y;
	int d;
};

car cars[500002];

bool compare(const car &a, const car &b) {
	return a.d < b.d;
}

int main() {
	scanf("%d", &n);
	for (int i=0; i<n;i++) {
		scanf("%d %d %d", &r, &w, &t);
		cars[i].type = r;
		if (r == 1) {
			cars[i].x = w;
			cars[i].y = -t;
			cars[i].d = w - t;
		} else {
			cars[i].y = w;
			cars[i].x = -t;
			cars[i].d = w - t;
		}
		// printf("car%d: (%d,%d) d:%d, type:%d\n", i, cars[i].x, cars[i].y, cars[i].d, cars[i].type);
	}

	sort(cars, cars+n, compare);

	int c1 = 0;
	int c2 = 0;
	int val = 1<<31; 
	int result = 0;

	for (int i = 0; i < n; ++i) {
		// printf("val %d: c1 %d c2 %d\n", val, c1, c2);
		if(cars[i].d != val) {
			val = cars[i].d;
			result += c1 < c2 ? c1 : c2; 
			c1 = c2 = 0;
		} 
		cars[i].type == 1 ? c1++ : c2++;
	}
	result += c1 < c2 ? c1 : c2; 

	printf("%d\n", result);

	return 0;
}