以下是我今天解题的题解报告:
[1] 圆桌问题
Problem Description
圆桌上围坐着2n个人。其中n个人是好人,另外n个人是坏人。如果从第一个人开始数数,数到第m个人,则立即处死该人;然后从被处死的人之后开始数数,再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位,能使得在处死n个人之后,圆桌上围坐的剩余的n个人全是好人。

Input
多组数据,每组数据输入:好人和坏人的人数n(<=32767)、步长m(<=32767);

Output
对于每一组数据,输出2n个大写字母,‘G’表示好人,‘B’表示坏人,50个字母为一行,不允许出现空白字符。相邻数据间留有一空行。

Sample Input
2 3
2 4
Sample Output
GBBG

BGGB

解释:用vector保存圆桌上的每个人,用vis数组标记这个人是不是坏人(1),循环n次找n个坏人,对cnt进行分类讨论,如果超过当前人数就取模,
注意相邻的输出空一行

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100000
int n,m;
vector<int> v;
int vis[N];
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        v.clear();
        memset(vis,0,sizeof(vis));
        int now=2*n;//总共的人数,下标从0开始 
        
        for(int i=0;i<now;i++)//初始化vector数组 
          v.push_back(i);
          
        int cnt=0;  
          for(int i=0;i<n;i++)
          {
              cnt=cnt+m-1;//当前的坏人
            if(cnt<now)
            {
                vis[v[cnt]]=1;//坏人标记为1 
                v.erase(v.begin()+cnt);
            } 
            else 
            {
                cnt=cnt%now;
                vis[v[cnt]]=1;//坏人标记为1 
                v.erase(v.begin()+cnt);
            }
            now--;
          }
          
          for(int i=0;i<2*n;i++)
          {
              if(i%50==0 && i!=0)
                  printf("\n");
              if(vis[i])
                printf("B");
                 else 
                   printf("G");
          }
          printf("\n\n");
    }
    return 0;
}

[2] Surround the Trees
There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.

There are no more than 100 trees.

Input
The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.

Output
The minimal length of the rope. The precision should be 10^-2.

Sample Input
9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0

Sample Output
243.06

思路
凸包模板题,题意就是计算凸包的周长,答案不用四舍五入,
要注意n=1时要加特判,n=2可以简化运算,
就先得到凸包中的点,在进行计算。重点在于如何得到点,利用向量的叉乘cross计算得到上凸包和下凸包之后合起来就是整个凸包,这里将其包括在convex函数里,或者也可以写在主函数里,用getdis来计算向量的模相加得到周长

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

struct Nodes{
	int x,y;
	Nodes(){}
	Nodes(int a,int b):x(a),y(b){}
	bool operator<(const Nodes& b)
	{
		if(x == b.x) return y>b.y;
		return x>b.x;
	} 
	Nodes operator - (const Nodes& b){
		return Nodes(x-b.x,y-b.y);
	}
};

struct Nodes P[110],ans[110];

int Cross(Nodes a, Nodes b)
{
	return a.x*b.y-a.y*b.x;
}

double getdis(Nodes a,Nodes b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int convex(Nodes* p,int n,Nodes* ch)
{
	sort(p,p+n);
	int m = 0;
	for(int i = 0 ; i < n; i++)
	{
		while(m > 1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
		ch[m++] = p[i];
	}
	int k = m;
	for(int i = n-2 ; i >= 0 ; i--)
	{
		while(m > k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
		ch[m++] = p[i];
	}
	if(n>1) m--;
	return m;
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF && n!=0)
	{
		for(int i = 0 ; i < n ; i++)
		{
			scanf("%d %d",&P[i].x,&P[i].y);
		}
		if(n == 1)
		{
			printf("0.00\n");
			continue;
		}
		if(n == 2)
		{
			printf("%.2f\n",getdis(P[0],P[1])*2);
			continue;
		}
		int cnt = convex(P,n,ans);
		double sum = 0;
		for(int i = 0 ; i < cnt ; i++)
		{
			sum += getdis(ans[i],ans[i+1]);
		}
		printf("%.2f\n",sum);
	}
    return 0;
}