luogu#P3875. [TJOI2010] 被污染的河流

[TJOI2010] 被污染的河流

题目背景

有一座城市,城市里有许多条人工河,河流的流向都是水平或者竖直的。为了方便市民用水,政府将河流设计成网格状。在水平方向上和竖直方向上,相邻河流的距离都是 11 公里。河流围出许多格子,每个格子就是一个社区,社区里的居民可以到社区周边四条河段中的任意一处打水喝。

题目描述

郁闷的是,不久之后,有些不法商人修建了工厂,污染了河流。河边许多居民喝了被污染的水,生病了。政府派出专员小强调查污染情况。地理专家小强行动迅速,很快给出了污染分布。他给出了一张污染清单。清单列出了被污染的河段,所有能喝到该河段水的居民都有可能生病(河段的端点处忽略不计)。但是,笨笨的小强怎么也算不出具体会有多少个社区的居民会生病,所以,他请你来帮帮忙。

输入格式

输入文件的第一行是一个整数 NN,表示被污染的河段的数目。

接下来 NN 行,每行 44 个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示被污染河段的起始位置和结束位置。每行输入的两个位置保证不重合,并且满足 x1=x2x_1=x_2y1=y2y_1=y_2

输出格式

输出一个整数 AA,表示有 AA 个社区的居民会喝到被污染的水。

3
1 3 4 3
6 7 6 3
4 6 7 6

16

提示

  • 对于 10%10\% 的数据,1x1,y1,x2,y21001 \le x_1,y_1,x_2,y_2 \le 1001N1001\le N \le 100
  • 对于 30%30\% 的数据,1x1,y1,x2,y21041 \le x_1,y_1,x_2,y_2 \le 10^41N1001\le N \le 100
  • 对于 100%100\% 的数据,1x1,y1,x2,y21051 \le x_1,y_1,x_2,y_2 \le 10^51N1041\le N \le 10^4