NOI 2003 卫星探测

这道题我的方法是二分判断+计算几何。

首先要找到多边形的边界，可以用四个点分别表示多边形上下左右边界的一个顶点。寻找边界可以用二分的方法。由于已知原点一定在多边形内或边上，寻找左边界就可以从x取值-10000到0之间二分答案，其余边界以此类推。

确定边界后，接着要确定每个每个顶点的位置，由于这是一个凸多边形，而且没有边与坐标轴平行，所以从左界点到下界点之间的一段折线斜率一定是严格单调递增的，类似的相邻两个边界点之间的一段折线的斜率也都是单调的。于是我们可以二分答案，确定折线每条线段的端点。最后在按照极角排序好的顶点顺序求出多边形面积，顺序输出每个顶点坐标。其实再写程序时如果求折线端点的顺序恰当，顶点就是直接排好的。

为了尽量减少询问次数，可以把已经询问过的记录下来，以免重复询问。计算几何题一般来说细节较多，代码量大，很难一次写对。再加上这是一个交互式题，我调了好长时间。由于询问次数的限制，我的程序不能拿到满分，后面有几个点都是8分9分。谁要是能写出满分的程序，我一定拜读。

/* 
 * Problem: NOI2003 detect
 * Author: Guo Jiabao
 * Time: 2009.5.26 13:30
 * State: Solved
 * Memo: 交互式 二分 凸多边形面积
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include "detect_lib.h"
using namespace std;
const int MAXB=10000,MAXL=20001,MAXN=201;
const double zero=1e-6;
struct point
{
	double x,y;
}LB,RB,BB,TB,V[MAXN],V2[MAXN];
struct ask
{
	int acnt;
	double v1,v2;
}AX0[MAXL],AY0[MAXL],*Ax,*Ay;
int N,N2;
double (*opt)(double,double) ;
double min(double a,double b)
{
	if (a==MAXB+1) return b;
	if (b==MAXB+1) return a;
	return a<b?a:b;
}
double max(double a,double b)
{
	if (a==MAXB+1) return b;
	if (b==MAXB+1) return a;
	return a>b?a:b;
}
void init()
{
	Ax=AX0+MAXB; Ay=AY0+MAXB;
	prog_initialize();
	for (int i=-MAXB;i<=MAXB;i++)
		Ax[i].acnt=Ay[i].acnt=-1;
}
ask Ask(int k,bool x)
{
	if (x)
	{
		if (Ax[k].acnt==-1)
			Ax[k].acnt=ask_x(k, &Ax[k].v1, &Ax[k].v2);
		if (Ax[k].acnt==1)
			Ax[k].v2=MAXB+1;
		return Ax[k];
	}
	else
	{
		if (Ay[k].acnt==-1)
			Ay[k].acnt=ask_y(k, &Ay[k].v1, &Ay[k].v2);
		if (Ay[k].acnt==1)
			Ay[k].v2=MAXB+1;
		return Ay[k];
	}
}
int BS_inc(int a,int b,bool x)
{
	int m;ask A;
	while (a<=b)
	{
		m=(a+b)>>1;
		A=Ask(m,x);
		if (A.acnt==0)
			a=m+1;
		else if (A.acnt==2)
			b=m-1;
		else
			return m;
	}
}
int BS_dec(int a,int b,bool x)
{
	int m;ask A;
	while (a<=b)
	{
		m=(a+b)>>1;
		A=Ask(m,x);
		if (A.acnt==0)
			b=m-1;
		else if (A.acnt==2)
			a=m+1;
		else
			return m;
	}
}
void Boundary()
{
	LB.y=Ax[ (int)(LB.x=BS_inc(-MAXB,0,true)) ].v1;
	BB.x=Ay[ (int)(BB.y=BS_inc(-MAXB,0,false))].v1;
	RB.y=Ax[ (int)(RB.x=BS_dec(0,MAXB,true))  ].v1;
	TB.x=Ay[ (int)(TB.y=BS_dec(0,MAXB,false)) ].v1;
}
double FP(point p1,point p2)
{
	return (p1.x * p2.y)-(p2.x * p1.y);
}
inline bool online(point p1,point p2,point p3,point p4)
{
	point r1,r2;
	r1.x=p1.x-p2.x; r1.y=p1.y-p2.y;
	r2.x=p3.x-p4.x; r2.y=p3.y-p4.y;
	return fabs(FP(r1,r2))<zero;
}
bool check(int p,int m)
{
	point p1,p2,r1,r2;
	ask A;
	r1.x=p; r2.x=p+1;
	A=Ask(p,true);
	r1.y=opt(A.v1,A.v2);
	A=Ask(p+1,true);
	r2.y=opt(A.v1,A.v2);
	p1.x=m; p2.x=m+1;
	A=Ask(m,true);
	p1.y=opt(A.v1,A.v2);
	A=Ask(m+1,true);
	p2.y=opt(A.v1,A.v2);
	return !online(r1,r2,p1,p2);
}
int BS(int a,int b,int p)
{
	int m;
	if (a>b || !check(p,b))
		return MAXB+1;
	while (a+1<b)
	{
		m=(a+b)>>1;
		if (check(p,m))
			b=m;
		else
			a=m+1;
	}
	if (check(p,a))
		b=a;
	return b;
}
void Vertex()
{
	int x,x1;
	V[++N]=LB;
	opt=min;
	for (x=LB.x;x<BB.x;x=x1)
	{
		x1=BS(x+1,BB.x-1,x);
		if (x1==MAXB+1) break;
		V[++N].x=x1;
		V[N].y=opt(Ax[x1].v1,Ax[x1].v2);
	}
	if (BB.x!=LB.x || BB.y!=LB.y)
		V[++N]=BB;
	for (x=BB.x;x<RB.x;x=x1)
	{
		x1=BS(x+1,RB.x-1,x);
		if (x1==MAXB+1) break;
		V[++N].x=x1;
		V[N].y=opt(Ax[x1].v1,Ax[x1].v2);
	}
	opt=max;
	for (x=LB.x;x<TB.x;x=x1)
	{
		x1=BS(x+1,TB.x-1,x);
		if (x1==MAXB+1) break;
		V2[++N2].x=x1;
		V2[N2].y=opt(Ax[x1].v1,Ax[x1].v2);
	}
	if (TB.x!=LB.x || TB.y!=LB.y)
		V2[++N2]=TB;
	for (x=TB.x;x<RB.x;x=x1)
	{
		x1=BS(x+1,RB.x-1,x);
		if (x1==MAXB+1) break;
		V2[++N2].x=x1;
		V2[N2].y=opt(Ax[x1].v1,Ax[x1].v2);
	}
	if ((BB.x!=RB.x || BB.y!=RB.y)&&(TB.x!=RB.x || TB.y!=RB.y))
		V2[++N2]=RB;
	for (;N2>=1;N2--)
		V[++N]=V2[N2];
}
void Square()
{
	int i;
	double S=0,k;
	for (i=1;i<N;i++)
	{
		k=FP(V[i],V[i+1]);
		if (k<0) k=-k;
		S+=k;
	}
	k=FP(V[N],V[1]);
	if (k<0) k=-k;
	S+=k;
	S/=2;
	ret_area(S);
}
void solve()
{
	Boundary();
	Vertex();
	Square();
	ret_n(N);
	for (int i=1;i<=N;i++)
		ret_vertex(V[i].x,V[i].y);
}
int main()
{
	init();
	solve();
	return 0;
}

<h2><span class="mw-headline">卫星探测 </span></h2>

【问题描述】

A国最近检测到了B国内有不正常的辐射，经调查发现，这是因为B国正在耗资百亿研制新式武器——连环阵。可是，由于B国对此武器的高度保密 措施，A国的间谍甚至无法确定出连环阵的具体位置。不过，A国的卫星还是可以找出连环阵所在的基地的。我们现在知道该基地是一个边上含有放射性物质的凸多 边形。经研究发现，在这个凸多边形所在的平面内，它具有如下性质：

包含坐标原点；
任意两条边不在同一直线上；
没有和x轴或y轴平行的边；
所有顶点的x坐标和y坐标都是整数。

现在A国可以通过卫星发出无限大的扇形探测波，与该凸多边形所在平面交于一条直线。不过该直线不是与x轴平行，就是与y轴平行。通过反射信号，我们可以确定该直线与凸多边形的交点个数和所有交点的坐标（如果有的话）。

现在，需要你写一个程序，通过控制卫星发出的探测波来确定这个凸多边形。

【交互方法】

本题是一道交互式题目，你的程序应当和测试库进行交互，而不得访问任何文件。测试库提供3组函数，分别用于程序的初始化，与测试库的交互，以及返回结果。它们的用法与作用如下：
prog_initialize必须先调用，但只能调用一次，用作初始化测试库；
测试库提供两个函数ask_x和ask_y作为与测试库交互的方式。其中ask_x(x0, y1, y2)的的作用是询问直线x=x0和多边形的交点，ask_y(y0, x1, x2)的作用是询问直线y=y0与多边形的交点，函数的返回值是交点的个数。ask_x(x0, y1, y2)调用后，y1和y2被赋值为交点的y坐标；ask_y(y0, x1, x2)调用后，x1和x2被赋值为交点的x坐标。如果只有一个交点，那么x1和x2或y1和y2的值相同；如果没有交点，那么x1和x2或y1和y2的值没有意义。
最后的一组函数是你的程序用来向测试库返回结果的。这里包括返回多边形面积的ret_area(s)，返回多边形顶点数目的 ret_n(n)，返回多边形顶点坐标的ret_vertex(x, y)。需要注意的事，这里ret_area是必须先于ret_n调用的，而ret_n又是必须先于ret_vertex调用的。不合适的调用方式将会强制你的程序非法退出。这里你需要在调用ret_n后调用n次ret_vertex返回多边形的顶点，但需要注意的是，如果你用ret_n返回的结果是错误的，那么测试库将会马上终止你的程序，并不接受下面的结果；同样的，如果ret_vertex中返回了错误的结果，那么测试库也会马上终止你的程序。如果 ret_vertex的结果均是正确的，那么测试库将会在你返回最后一个顶点坐标后终止你的程序。

注意：你需要按照逆时针顺序返回所有顶点的坐标，不过你可以从任意一个顶点开始。

【对使用Pascal选手的提示】

你的程序应当使用如下的语句引用测试库。

uses detect_lib;

测试库使用的函数原型为：

procedure prog_initialize;
  function ask_x(const x0: longint; var y1, y2: double): longint;
  function ask_y(const y0: longint; var x1, x2: double): longint;
  procedure ret_area(const s: double);
  procedure ret_n(const n: longint);
  procedure ret_vertex(const x, y:longint);

【对使用C/C++选手的提示】

你应当建立一个工程，把文件libdetect.o包含进来，然后在程序头加上一行：

#include “detect_lib.h”

测试库使用的函数原型为：

void prog_initialize();
  int ask_x(int x0, double *y1, double *y2);
  int ask_y(int y0, double *x1, double *x2);
  void ret_area(double s);
  void ret_n(int n);
  void ret_vertex(int x, int y);

【数据说明】

如果凸多边形的坐标如图所示，那么一种可能得满分的调用方案如下：

Pascal选手的调用方法	C/C++选手的调用方法	说明
Prog_initialize;	prog_initialize();	初始化程序
ask_x(-6, y1, y2);	ask_x(-6, &y1, &y2);	返回值1，y₁=2，y₂=2
ask_x(-5, y1, y2);	ask_x(-5, &y1, &y2);	返回值2，y₁=3.4，y₂=-5
ask_y(2, x1, x2);	ask_y(2, &x1, &x2);	返回值2，x₁=-6，x₂=16
ask_y(-20, x1, x2)	ask_y(-20, &x1, &x2)	返回值0，x₁、x₂中的值无意义
ret_area(241.5);	ret_area(241.5);	返回面积
ret_n(5);	ret_n(5);	返回n
ret_vertex(8, -9);	ret_vertex(8, -9);	返回顶点(8, -9)
ret_vertex(16, 2);	ret_vertex(16, 2);	返回顶点(16, 2)
ret_vertex(-1, 9);	ret_vertex(-1, 9);	返回顶点(-1, 9)
ret_vertex(-6, 2);	ret_vertex(-6, 2);	返回顶点(-6, 2)
ret_vertex(-5, -5);	ret_vertex(-5, -5);	返回顶点(-5, -5)

注意，该例子只是对库函数的使用说明，并没有算法上的意义。

这里n最大为200，x、y坐标在[-10000, 10000]这个区间内。

【评分方法】

如果你的程序有下列情况之一，得0分：

访问了任何文件(包括临时文件)或者自行终止；
非法调用库函数；
让测试库异常退出。

否则每个测试点你的得分按这样来计算：包括顶点数提交正确的1分，面积提交正确的2分，顶点坐标完全正确的2分，分数累计。剩下的5分将根据你调用ask_x和ask_y的总次数进行评判，公式如下：

这里x为你的程序调用的ask_x和ask_y的次数，score为你的得分。

【你如何测试自己的程序】
在工作目录下建立一个文件叫做detect.in，文件的第一行包括一个整数n为顶点的数目，以下n行每行两个整数按照逆时针方向给出凸多边形的顶点坐标；
执行你的程序，此时测试库会产生输出文件detect.log，该文件中包括了你程序和库交互的记录和最后的结果；
如果程序正常结束，detect.log的最后一行会给出你的程序的分数；
如果程序非法退出，则我们不保证detect.log中的内容有意义。

上次修改时间 2017-05-22

相关日志