NOI 2003 衛星探測

本文正體字版由OpenCC轉換

這道題我的方法是二分判斷+計算幾何。

首先要找到多邊形的邊界，可以用四個點分別表示多邊形上下左右邊界的一個頂點。尋找邊界可以用二分的方法。由於已知原點一定在多邊形內或邊上，尋找左邊界就可以從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

相關日誌