50043. Mosaics
難度：4.5/5
定義2D向量的外積： \[a \times b = a_x \cdot b_y - a_y \cdot b_x = |a||b| \sin \theta\]
所以可以求由\(a\)到\(b\)的逆時針夾角是否在\(180 ^\circ\)內，若\(\theta \lt 180 ^\circ\)，則\(\sin \theta \gt 0\)，推得\(a \times b > 0\)，反之亦然。
這題好難...。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
58
59
60
61
62
63
64
65
66
67#include <stdio.h>
#include <stdlib.h>
#define swap(x, y){int t = x; x = y; y = t;}
typedef struct _coor{
int x;
int y;
} _coor;
int max(int a, int b, int c){
int max_num = a;
if(b > max_num) max_num = b;
if(c > max_num) max_num = c;
return max_num;
}
int min(int a, int b, int c){
int min_num = a;
if(b < min_num) min_num = b;
if(c < min_num) min_num = c;
return min_num;
}
int sign(int x1, int y1, int x2, int y2, int x3, int y3){
long long ax = x2 - x1;
long long ay = y2 - y1;
long long bx = x3 - x1;
long long by = y3 - y1;
long long ans = ax * by - ay * bx;
if(ans > 0) return 1;
else if(ans == 0) return 0;
else return -1;
}
int main(){
int x1, y1, x2, y2, x3, y3;
scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3);
int max_x = max(x1, x2, x3);
int min_x = min(x1, x2, x3);
int max_y = max(y1, y2, y3);
int min_y = min(y1, y2, y3);
int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1};
int cnt = 0;
for(int i = min_x; i <= max_x; i++){
for(int j = min_y; j <= max_y; j++){
int c = 0;
for(int k = 0; k < 4; k++){
int x = i + dx[k], y = j + dy[k];
int d1 = sign(x, y, x1, y1, x2, y2);
int d2 = sign(x, y, x2, y2, x3, y3);
int d3 = sign(x, y, x3, y3, x1, y1);
if((d1 >= 0 && d2 >= 0 && d3 >= 0) ||
(d1 <= 0 && d2 <= 0 && d3 <= 0)){
c++;
}
}
if(c == 4) cnt += 1;
}
}
printf("%d\n", cnt);
}