ACM

POJ 2187 Beauty Contest(计算几何-旋转卡壳)

POJ 2187 Beauty Contest(计算几何-旋转卡壳)
题意:给出一个多边形,求出多边形最远两点距离的平方。题解:旋转卡壳模板题,先求凸包再用Andrew求最远点对即可。代码:StatusAcceptedTime219msMemory3128kBLength2774LangG++#include <iostream> #include <cstdio> #include <cstring&... 继续阅读 »
ACM

POJ - 1113 Wall(计算几何-凸包)

POJ - 1113 Wall(计算几何-凸包)
题意:给出一个多边形,在距离这个多边形最低为L的地方建立一堵墙,求这墙的周长。题解:对圆角加起来为什么是个圆很不理解,所以就看了kuangbin巨巨的题解。这道题的答案是凸包周长加上一个圆周长,即包围凸包的一个圆角多边形,但是没弄明白那些圆角加起来为什么恰好是一个圆。每个圆角是以凸包对应的顶点为圆心,给定的L为半径,与相邻两条边的切点之间的一段圆弧。每个圆弧的两条半径夹角与对应的凸包的内角互补。假... 继续阅读 »
ACM

POJ 2653 Pick-up sticks(计算几何-线段交)

POJ 2653 Pick-up sticks(计算几何-线段交)
题意:依次给出n根木棍,后放的木棍可能会覆盖前面的木棍,求没有被覆盖的木棍的序号。题解:枚举线段相交即可,由于题目给出的数据是不可能存在1000根木棍在最上面,所以可以直接暴力枚举(但是题目没说是任何时候都没有1000根木棍在上面啊,感觉数据有点迷)。然后看别人还有用队列来做的,很神奇,就学习了一波。代码:StatusAcceptedTime657msMemory5920kBLength2013L... 继续阅读 »
ACM

POJ 1556 The Doors(计算几何+最短路)

POJ 1556 The Doors(计算几何+最短路)
题意:一个10*10的正方形房间内,有一些墙壁,这些墙壁会有两个通道,现在要从点(0 ,5)出发,到达(10,5)。求最短路径。输入描述:第一行给出墙壁的数量n。接下来n行每行包括5个整数,x,y1,y2,y3,y4,分别代表墙的x坐标(给出的x坐标是递增序),以及两个通道两端的y坐标。当n等于-1时结束程序。题解:我们把一个墙壁看作是三条线段的组成,起始、结束、以及每个墙壁两个通道的两端看作是点... 继续阅读 »
ACM

POJ 1269 Intersecting Lines(计算几何-两直线位置关系)

POJ 1269 Intersecting Lines(计算几何-两直线位置关系)
题意:给出你两条直线,求出这两条直线的关系,平行输出NONE,重合输出LINE, 相交输出交点POINT x y题解:模板题,理解直线关系的求法即可。代码:#include <iostream> #include <cstdio> #include <cstring> #include ... 继续阅读 »
ACM

HDU 5527 Too Rich(贪心好题)

HDU 5527 Too Rich(贪心好题)
题意:给出你硬币价值分别为1,5,10,20,50,100,200,500,1000,2000的数量,请找出能凑成价值为p的硬币最多的方案,输出此时的硬币数量。题解:假设我们不考虑50,500这两个数,那么,其他的数都是前一个数的倍数,因此,只要前面有足够的硬币剩余,我们就可以将后面的硬币转换成前面的硬币来增加硬币数量。但是现在这里的50和500改变了这一性质,所以我们考虑改进这一贪心方法。方法一... 继续阅读 »
ACM

HDU 5534 Partial Tree (完全背包)

HDU 5534 Partial Tree (完全背包)
题意:给出你n个节点,请添加n-1条边使得它变成一棵树。这个树必须足够“酷”,每个节点的“酷”值的定义为对于一个度数为x的节点,那么它的一个价值为f(x),求所有节点最大的酷值和。题解:dp好题。假设我们考虑到每个点还剩多少度这样分配,那么时间复杂度为O(n3),明显GG,于是我们考虑将每个点预先分配一度,由于总度数是2n-2,那么就剩下n-2度需要分配。于是我们可以将其他度数的f值变成与度数为1... 继续阅读 »
ACM

POJ 3304 Segments(计算几何)

POJ 3304 Segments(计算几何)
题意:给出n条线段两个端点的坐标,问所有线段投影到一条直线上,如果这些所有投影至少相交于一点就输出Yes!,否则输出No!。题解:假设存在一条这样的直线,那么过这条直线的公共投影区域作一条垂线,则该垂线必定与所有线段相交。所以问题变成了如何找这一条直线,然后这条直线必过线段的两个端点。考虑到线段数目不是很多,所以我们只需要枚举所有线段的两个端点组成的直线即可。注意用精度判断点是否重合!代码:#in... 继续阅读 »
ACM

POJ 2318,2398 TOYS |Toy Storage (计算几何)

POJ 2318,2398 TOYS |Toy Storage (计算几何)
题意:有一个抽屉,放入n块按照x轴排序的不相交的隔板,分成n+1块区域,然后在给出m个玩具,统计每个区域的玩具个数。数据解释:n代表隔板数目,m是玩具数目,x1,y1是抽屉左上角坐标,x2,y2是抽屉右下角坐标。接下来给出n块板子的顶部x坐标ui,底部x坐标li。接下来给出m个玩具的坐标xi, yi。题解:由于线段已经排序并且不相交,所以直接二分判断每个玩具坐标点处于直线的左右侧即可。POJ239... 继续阅读 »
ACM

51nod 1265 四点共面(计算几何)

51nod 1265 四点共面(计算几何)
题意:给出三维空间上的四个点(点与点的位置均不相同),判断这4个点是否在同一个平面内(4点共线也算共面)。如果共面,输出"Yes",否则输出"No"。题解:很容易想到,如果四点共面,那么从分别从两个对点出发的两个向量的叉积必然平行。然后就是代码模板套上即可。代码:#include <bits/stdc++.h> using ... 继续阅读 »