计算几何——从入门到不会

在队里负责计算几何部分,一直都没有开始自己的工作,非常羞愧。如今终于 ready to work,专门针对计算几何专题进行练习。这篇文章将不断更新,记录一些计算几何方面的题目。预计难度将会逐步加大,记录和总结也将越来越深入。

计算几何相关注意事项

  1. 注意题目让输入int型数据最好先直接输入int型数据,然后再赋给Point类中的double数据,因为直接输入double数据会比输入int慢很多(2s的题TLE换成输入int之后300ms直接AC)
  2. 输出的时候尽量用printf,速度快且避免很多不必要的错误
  3. 判断直线平行不要求斜率,直接用叉积,避免除号
  4. 涉及比较大小的时候一定要用eps——dcmp(),精度问题十分重要

 

 

 

 

 

updated Sunday,11 June 2017

POJ2318.Toys

Description

Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem – their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.John’s parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

Input

The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.

Output

The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

Sample Input

Sample Output

Hint

As the example illustrates, toys that fall on the boundary of the box are “in” the box.
题目分析:这是一道计算几何入门题目,题意给出一个长方形区域,这个区域被几条线段分割成几个小区域,统计这几个区域内每个区域包含点的个数。题目规定点不会与分界线重合,并且分界线的输入是按顺序的。
一开始考虑比较每个点与线段端点之间的关系,分多种情况讨论点和线段之间的关系,后来发现实在太复杂, 并且复杂度方面可能较高。然后考虑到求点在线段上的投影,投影点的横坐标如果在点的左边,则该线段在点的左边,这样来判断点和直线的关系,再加上分界线的输入是按顺序的,直接暴力求第一个在所求点左边的线段,然后将该线段右侧区域的点个数加一,应该是可行的。
求点在线段上的投影公式如下:

{\mbox{proj}}_{{[{\vec {s}}\,]}}({{\vec {v}}})={\frac {{\vec {v}}\cdot {\vec {s}}}{{\vec {s}}\cdot {\vec {s}}}}{\vec {s}}

代码如下:

 

这时觉得复杂度可能稍微有些高,但考虑到题目n=5000,m=5000,O(n*m)的复杂度似乎是可以接受的,然后果断T了。
接着用二分优化,结果卡了很久,一开始发现自己开头写错了一个字母,很蠢,改正后仍然输不出结果。这个地方有一个比较坑的点在于这个求投影的函数在线段垂直的时候是求不出答案的,发现之后立刻解决,Accept。
AC代码:

 

 

update  Saturday,8 July 2017

Poj1269.Intersecting Lines

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 15992 Accepted: 6923

Description

We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.
Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.

Input

The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4).

Output

There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read “END OF OUTPUT”.

Sample Input

Sample Output

 

今天又重新开始做计算几何,把之前做过的两道题又做了一遍,发现了一些问题,又做了一道新的线段相交的题,也就是上边的这道题。这可以说是很水得一道题,给两条直线,判断他们之间的关系。但是我却一直WA,一开始用的斜率,后来改成了用叉积判断是否平行。这都没用,一直WA,最后把所有的cout改成了printf,就过了,感觉很神奇,以后关于这种输出最好都用C的函数。

代码如下:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注