Question

acm一道计算几何问题，请求指点思路

交互题，有一个顶点为整点的三角形，我们不知道顶点具体坐标，但现在的任务就是确定这三个坐标。你可以调用函数Q(x1,y1,x2,y2)，表示询问三角形对(x1,y1),(x2,y2)所确定的有向直线的相对位置。如果返回1，表示完全在这条直线的左方，返回2表示完全在右方，返回3表示直线和三角形有至少一个交点。三角形的坐标绝对值不大于10^5，你的询问坐标绝对值不能大于4.2x10^5，且不能询问超过600次。

Answer 1

我建议分两步做.
第一步先用水平和竖直的直线去探测出包含该三角形且边与坐标系平行的最小矩形, 也就是探测min{x1,x2,x3}, max{x1,x2,x3}, min{y1,y2,y3}, max{y1,y2,y3}这四个数. 利用二分法, 每个数只需要十几次检测就能得到.
第二步是在矩形的四条边上探测三角形的顶点, 同样是用二分法. 具体的探测方法如下. 比如说, 第一步得到的矩形左下角为(a,b), 右上角为(c,d). 要探测最左边的直线x=a上的三角形顶点(可能有两个), 可以选用形如(x1,y1,x2,y2)=(a,y1,a+1,c-1)和(x1,y1,x2,y2)=(a,y1,a+1,d+1)这样的探测直线.
当然, 第二步里你可以把特殊情况(和矩形有两条或一条边共线)分开探测, 总之就是写之前想清楚, 不要遗漏什么情况.