//136K 0MS C++
#include <cstdio>
#include <cstring>
struct Line {
int bx, ex;
int by, ey;
};
typedef struct Line Line;
Line hLine[110];
Line vLine[110];
int caseNum;
int LineNum;
bool insect(Line & vline, Line & hline) {
// printf("VV %d %d %d %d\n", vline.bx, vline.by, vline.ex, vline.ey);
// printf("LL %d %d %d %d\n", hline.bx, hline.by, hline.ex, hline.ey);
return (vline.by <= hline.by) &&
(vline.ey >= hline.by) &&
(hline.bx <= vline.bx) &&
(hline.ex >= vline.bx);
}
int main() {
scanf("%d", &caseNum);
for (int i = 1; i <= caseNum; i++) {
scanf("%d", &LineNum);
int vLineNum = 0;
int lLineNum = 0;
for (int j = 0; j < LineNum; j++) {
int x1, x2, y1, y2;
scanf("%d %d %d %d",
&x1, &y1, &x2, &y2);
if (x1 == x2) {
if (y1 > y2) {
int tmp = y1;
y1 = y2;
y2 = tmp;
}
// printf("v %d %d %d %d\n", x1, y1, x2, y2);
vLine[vLineNum].bx = x1;
vLine[vLineNum].ex = x2;
vLine[vLineNum].by = y1;
vLine[vLineNum].ey = y2;
vLineNum++;
} else if (y1 == y1) {
if (x1 > x2) {
int tmp = x1;
x1 = x2;
x2 = tmp;
}
// printf("h %d %d %d %d\n", x1, y1, x2, y2);
hLine[lLineNum].bx = x1;
hLine[lLineNum].ex = x2;
hLine[lLineNum].by = y1;
hLine[lLineNum].ey = y2;
lLineNum++;
}
}
int res = 0;
// printf("%d %d\n", vLineNum, lLineNum);
for (int i = 0; i < vLineNum; i++) {
for (int j = 0; j < lLineNum; j++) {
if (insect(vLine[i], hLine[j])) {
// printf("AA %d %d\n", i, j);
for (int q = i + 1; q < vLineNum; q++) {
if (insect(vLine[q], hLine[j])) {
for (int p = j + 1; p < lLineNum; p++) {
if (insect(vLine[i], hLine[p]) &&
insect(vLine[q], hLine[p])) {
res++;
}
}
}
}
}
}
}
printf("%d\n", res);
}
}
今天看了某神的题解,我了个去,四条线段交出一个矩形,每一个矩形都是由四条线段交出来的啊!!!
而且题目中说每个交点都是唯一水平和垂直线交出来的,言外之意没有重合的线段。
茅厕顿开。如果对于线段不好想的话就想直线好了,任意一个矩形都会由四条直线围出来。
那这道题就是暴力枚举四条线段,看能相互相交不,能相交就多一个矩形,最后输出就好了。
不过枚举是最考讲究的活,应该是枚举一条水平,一条垂直,一条平,一条垂直。
虽然是用暴力解得,但还是要能想到上面的才行.
标签:int,vLineNum,lLineNum,hLine,poj,1693,y1,vLine From: https://blog.51cto.com/u_9420214/6333002