> 听说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中表现貌似很惨。

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