首页 > 其他分享 >poj-1693

poj-1693

时间:2023-05-23 16:00:29浏览次数:38  
标签:int vLineNum lLineNum hLine poj 1693 y1 vLine


//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

相关文章

  • POJ1737 Connected Graph ( n点无向连通图计数
    题意说明:求\(n\)个点的无向连通图个数据说已经非常典了,但是我太菜了不会组合数学,最近补档时看到这道题,决定记录下来理理思路......
  • POJ--1163 The Triangle(DP)
    记录10:432023-5-15http://poj.org/problem?id=1163reference:《挑战程序设计竞赛(第2版)》第二章练习题索引p135DescriptionFigure1showsanumbertriangle.Writeaprogramthatcalculatesthehighestsumofnumberspassedonaroutethatstartsatthetopa......
  • 实验六-Salt本地pojie实验
    【实验目的】了解Salt型密码的加密机制,学会使用本地密码pojie工具来pojieSalt型密码,了解pojie密码原理。【知识点】Salt,密码pojie【实验原理】1.Salt概念在密码保护技术中,salt是用来修改口令散列的随机数据串。可将salt加入散列,即使系统的另一用户也选用了同一口令,也可通过唯......
  • POJ 动态规划题目列表
    声明:1.这份列表当然不是我原创的,从文库里下载了一份,放到这里便于自己浏览和查找题目。※最近更新:Poj斜率优化题目1180,2018,3709列表一:经典题目题号:容易:1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1191,1208, 1276, 1322, 1414, 1456, 1458......
  • poj018(2)
    再贴一版poj1018,其实与之前的那一版差不多,只是去掉了注释,这样可能看起来会舒服一点packagecom.njupt.acm;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.Arrays;importjava.util.Scanner;publicclassTestPOJ1018{pu......
  • poj1018(1)
    其实这道题我也没有完全的弄明白,糊里糊涂就ac了 大致题意:某公司要建立一套通信系统,该通信系统需要n种设备,而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产,而每个厂家生产的同种设备都会存在两个方面的差别:带宽bandwidths和价格prices。现在每种设备都各需要1个,考虑......
  • poj1013
    大致题意:有一打(12枚)硬币,其中有且仅有1枚假币,11枚真币用A~L作为各个硬币的代号假币可能比真币略轻,也可能略重现在利用天枰,根据Input输入的3次称量,找出假币,并输出假币是轻还是重。 解题思路:模拟法要考虑的情况较繁琐,可利用简单的逻辑推理进行解题。  注意Input一行代......
  • POJ2739 Sum of Consecutive Prime Numbers&&Acwing4938 连续质数之和
    方法:单调队列为什么是单调队列?因为这里让我们求连续的质数和,我们可以利用欧拉筛来维护质数,再利用单调队列来维护连续的质数。代码(POJ不支持C++11差评):#include<cstdlib>#include<cstring>#include<cstdio>#include<cctype>namespaceFastIo{ #definegcgetchar() #d......
  • color a tree poj2054
    coloratree(贪心)题目描述可以得到一个确定性的结论,最大值的结点一定是在父节点染色后立即染色。但是此时依结论不好在复杂的情况正推,先考虑简单情况:假如有权值x,y,z三个点,已知x,y一定一起染色,则有两种可能方案:先x,y,再z,代价为X=x+2y+3z先z,再x,y,代价为Y=2x+3y+zX-Y=2z-......
  • SPOJ COT3 Combat on a tree
    简要题意给定一棵有根树,初始有黑点白点。两人交替操作,每次选择一个白点,将这个点到根路径上所有点染黑,选不了则输。求先手能否必胜;如果能,给出第一步可能的所有走法。数据范围:\(1\len\le10^5\)。题解小清新题。难度不配黑题。进行一次操作以后,这个点到根路径上所有点两侧的子......