中南大学算法设计与分析实验报告.doc

姓名：
学号： 0909122824
班级： 信安1202
指导老师： 李敏

算法设计与分析基础
——实验报告

实验一 分治
—最近点对
一． 问题
Problem
Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.
Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

Input
The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

Output
For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

二． 分析思路

题目是给n个点的坐标，求距离最近的一对点之间距离的一半。第一行是一个数n表示有n个点，接下来n行是n个点的x坐标和y坐标。
首先，假设点是n个，编号为1到n。找一个中间的编号mid，先求出1到mid点的最近距离设为d1，还有mid+1到n的最近距离设为d2。如果说最近点对中的两点都在1-mid集合中，或者mid+1到n集合中，则d就是最小距离了。但是还有可能的是最近点对中的两点分属这两个集合，若存在，则把这个最近点对的距离记录下来，去更新d。这样就得到最小的距离d了。

三． 源代码
#include
#include
#include
using namespace std;

#define N 1000010

struct point
{
double x;
double y;
}p1[N],p2[N];

double dis ( point a , point b )
{
return sqrt( pow (a.x-b.x,2) + pow ( a.y-b.y,2 ) );
}

double min ( double a , double b )
{
return aint b )
{
return a.x < b.x ;
}
bool cpy ( point a , point b )
{
return a.y < b.y ;
}

double mindis ( int l , int r )
{
if( l + 1 == r )
return dis ( p1[l] ,p1[r] );
if( l + 2 == r )
return min ( dis ( p1[l] , p1[l+1] ) , min ( dis ( p1[l+1] , p1[r] ) , dis ( p1[l] , p1[r] ) ) );
else
{
int mid , count=0 ;
double mini;
mid = ( l + r) /2 ;
mini = min ( mindis ( l , mid ) , mindis ( mid+1 , r ) );
for( int i = l ; i <= r ; i++ )
{
if ( fabs ( p1[i].x - p1[mid].x ) <= mini )
p2[count++]=p1[i];
}
sort ( p2 , p2+count , cpy );
for ( int i=0 ; i < count ; i++ )
{
for ( int j = i+1; j < count ;j++)
{
if ( p2[j].y-p2[i].y>=mini)
break;
else
if(dis (p2[j],p2[i]) {
for(int i=0;ih straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.
A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.
The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

Input
The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.

Output
For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

二．分析思路
对于每个点，若能放置大炮则能选择放或者不放两种情况，若不能放置大炮则就只有一种情况。直接搜索，回溯的时候把点的状态恢复.

三．源代码
#include
#include
#include
#define MAX_SIZE 10

char map[MAX_SIZE][MAX_SIZE];
int d[4][2]={0,1,0,-1,1,0,-1,0};
int N,cnt;

int ok(int x, int y)
{
if(map[x][y]!='.')
return 0;
int i,xx,yy;
for(i=0;i<4;i++)
{
xx=x+d[i][0];
yy=y+d[i][1];
while(xx>=0 && xx=0 && yy];
yy+=d[i][1];
}
}
return 1;
}
int search(int x, int y, int c)
{
int i,j;
for(j=y;j for(j=0;jcnt)
cnt=c;
return 0;
}

int main()
{
int i;
while(scanf("%d",&N)&&N)
{
fori=0;i这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。
为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）

Input
输入数据有多组。每组数据的第一行为以正整数n(0[j-1],dp[i+1][j],dp[i+1][j-1])+pie[i][j]。pie[i][j]为时间i时在j位置掉的馅饼数目。

三．源代码
#include
#include
#include
#define MAX 100001

int pie[MAX][12];

int Max(int a, int b){
return (a > b) ? a : b;
}
int Max(int a, int b, int c){
int max = (a>b) ? a:b;
return (max>c) ? max:c;
}
int MaxNumOfPie(int max_time){
int i, j, max;
for (i = max_time - 1; i >= 0; --i){
pie[i][0] = Max(pie[i+1][0], pie[i+1][1]) + pie[i][0];
for (j = 1; j < 10; ++j){
pie[i][j] = Max(pie[i+1][j-1], pie[i+1][j], pie[i+1][j+1]) + pie[i][j];
}
pie[i][10] = Max(pie[i+1][10], pie[i+1][9]) + pie[i][10];
}
return pie[0][5];
}

int main(){
int n,time,location;
int max_time;
while (scanf("%d",&n) != EOF && n != 0){
memset(pie, 0, sizeof(pie));
max_time = -1;
for (int i=1; i<=n; ++i){
scanf ("%d%d", &location, &time);
++pie[time][location];
if (max_time < time)
max_time = time;
}
printf ("%d\n", MaxNumOfPie(max_time));
}
return 0;
}

四．运行结果