AcWing 759. 格子染色 python
原题链接
中等
作者:
caiwen
,
2020-03-29 22:39:00
,
所有人可见
,
阅读 830
from collections import defaultdict
n = int(input())
row_dict = defaultdict(list)
col_dict = defaultdict(list)
for _ in range(n):
a = list(map(int, input().split()))
if a[0] == a[2]:
col_dict[a[0]].append([min(a[1], a[3]), max(a[1], a[3])])
else:
row_dict[a[1]].append([min(a[0], a[2]), max(a[0], a[2])])
def merge(indexes): # 合并区间基本模板
indexes.sort(key=lambda x:x[0])
res = []
for index in indexes:
if not res or res[-1][1] < index[0]:
res.append(index)
else:
res[-1][1] = max(res[-1][1], index[1])
return res
def bin_search(k, intervals):
l, r = 0, len(intervals)-1
while l < r:
mid = (l+r+1)//2
if intervals[mid][0] <= k:
l = mid
else:
r = mid - 1
return l
def is_cross(row, col, row_intervals, col_intervals):
i = bin_search(row, col_intervals) # 二分快速查找对对比区间
j = bin_search(col, row_intervals)
if col_intervals[i][1] >= row >= col_intervals[i][0] and row_intervals[j][1] >= col >= row_intervals[j][0]:
return 1
return 0
for row in row_dict:
row_dict[row] = merge(row_dict[row])
for col in col_dict:
col_dict[col] = merge(col_dict[col])
insert_num = 0
for row in row_dict:
for col in col_dict:
insert_num += is_cross(row, col, row_dict[row], col_dict[col])
total_num = 0
for row in row_dict:
total_num += sum([i[1]-i[0]+1 for i in row_dict[row]])
for col in col_dict:
total_num += sum([i[1]-i[0]+1 for i in col_dict[col]])
print(total_num-insert_num)