听说NOIP要用NOILinux，我马不停蹄的开始了适应。
之所以用这题来练手，主要因为它比较简单...但是，想AC不容易。

安装NOILinux不是一个容易事，我采取了一个妥协的方法：
使用VMWare虚拟机。但是发现一个可怕的事情：虚拟机中文件无法
复制到物理机上。怎么办呢？
再次妥协：让虚拟机使用软盘，再用WinImage读取。

上次比赛时听说几个IDE均出现了问题，我就用gedit+g+++gdb来写程序

gedit 3246.cpp                     编辑
g++ 3246.cpp -o 3246 -Wall         编译，-Wall生成所有警告，挺实用的
./3246                             运行
g++ 3246.cpp -o 3246 -Wall -g      -g生成调试信息
gdb 3246                           调试

首先说说这题算法：
用GrahamScan扫描求出一个凸包，然后对每个凸包上的点：
去除它，
设凸包上它的前驱与后继为x,y，
把极角排序后位于x与y之间的点求个凸包，
计算面积。

问题一般出在移除最左下的那个“基准”点上，我的策略：
删了它，重新求凸包。

计算几何貌似是从来不卡常数的（也许有例外），于是我就写的比较工程，
判断方向、面积、排序都单独用比较一般的函数实现
int Direction(int i,int j,int k){
	long long t=(X[j]-X[i])*(Y[k]-Y[i])-(X[k]-X[i])*(Y[j]-Y[i]);
	if (t>0)return 1;
	if (t==0)return 0;
	return -1;
}
long long Dist(int a,int b){
	return (X[a]-X[b])*(X[a]-X[b])+(Y[a]-Y[b])*(Y[a]-Y[b]);
}
long long area(int a,int b){
	long long s=((X[a]-X[0])*(Y[b]-Y[0])-(X[b]-X[0])*(Y[a]-Y[0]));
	if (s<0)s=-s;
	return s;
}
void exchange(int a,int b){
	long long t;
	t=X[a];X[a]=X[b];X[b]=t;
	t=Y[a];Y[a]=Y[b];Y[b]=t;
}
void qs(int b,int e){
	if (b>=e)return;
	exchange(b,(b+e)>>1);
	int j;
	for (int i=j=b+1;i<=e;i++)if (Direction(0,i,b)==1 ||
					   Direction(0,i,b)==0 && Dist(0,i)<Dist(0,b))
		exchange(i,j++);
	exchange(--j,b);
	qs(b,j-1);qs(j+1,e);
}

剩下的扫描、主程序都比较简单了。
强烈提示wa的人：正确处理共线是一个AC的凸包的一半。
long long Scan(int b,int e,int *buf,int &m,int delta=-1){	
//delta这个点在扫描的时候将被忽略，相当于被删除
	m=1;buf[0]=0;
	for (int i=b;i<=e;i++)if (i!=delta){
		buf[m++]=i;
		while (m>3 && Direction(buf[m-2],buf[m-1],buf[m-3])==-1)
			buf[m-2]=buf[m-1],m--;
	}
	long long r;
	r=0;
	for (int i=1;i<m-1;i++)r+=area(buf[i],buf[i+1]);
	return r;
}

看一眼数据规模，是要用long long的。
这时候，一个很纠结的问题出现了：
如何输出long long?用哪种方式？
printf("%lld",a)//for Linux
printf("%I64d",a)//for POJ
cout<<a//...it's too slow
这个问题让我思考了很久，最终决定：自己写一个输出函数
void printll_(long long a){
        if (a!=0){
		printll_(a/(long long)10);
		printf("%d",int(a%(long long)10));
	}
}
void printll(long long a){
	if (a==0)printf("0");
	else if (a>0)printll_(a);
	else if (a<0){
		putchar('-');
		printll(-a);
	}
}

写好了，交上去，挂了。
怎么办？
随便编几个数据：
4 0 0 0 1 1 0 1 1
16 0 0 0 1 0 2 0 3 1 0 1 1 1 2 1 3 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3
4 0 0 100 0 1 0 1 1
4 0 0 100 0 0 1 1 1
4 0 0 0 100 1 0 1 1
4 0 0 1 0 0 1 100 100
结果，跑第三个数据的时候，输出49.50
赶紧调试，一想到有一个叫gdb的好东西，就不用自己的土鳖调试法了。
(gdb)break 84
(gdb)print a2
......
一直追踪到最后输出结果部分都是正确的。
在一看代码：
printll(a2/(long long)2);
怪不得，打错变量了。
printll(ret/(long long)2);
改，运行。
然而，最后一组数据挂了。
接着追踪，愕然发现：调用Scan忘记设置delta了。
接着修改，通过软盘拷贝出，提交...终于AC啦！

说一下用Linux我的几个习惯：
它有一个切换桌面的功能，于是，我就把系统管理、编程的窗口分到两个桌面上，
免去了很多麻烦！
编译、运行、调试都要用不同的命令，都挺长的......我就
各开一个终端，再次操作的时候按↑键再回车就可以了。
gdb真是个好东西！使用它可以让工作量大大降低。
不过，它在windows下的各个IDE中表现貌似很惨。

• "使用VMWare虚拟机。但是发现一个可怕的事情：虚拟机中文件无法 > 复制到物理机上。怎么办呢？" ----用virtualbox的“共享数据空间”。 (3096) BlueSkyThinker 2009-11-08 12:00:14
  • Re:"使用VMWare虚拟机。但是发现一个可怕的事情：虚拟机中文件无法 > 复制到物理机上。怎么办呢？" ----用virtualbox的“共享数据空间”。 (12) waaao 2012-06-29 21:52:44
• Win下gdb挺好用的 (53) resty 2009-11-08 12:06:04