POJ 1066 Treasure Hunt
这道题差点让我崩溃，排序排了一下午，崩溃的精度问题，查错查了一晚上，最后发现把Y写成X了，更悲剧，最后终于弄出来了，一定要和大家分享一下~~~~~~
有好的意见，一定要留言呀！
链接：http://poj.org/problem?id=1066
知识点；叉积
题意：给定一个矩形，内有N个内墙，且墙的两个端点在矩形的两条边上，形成了很多小室，有一个宝藏（点），要想到达宝藏所在地，必须穿过小室的
门的中点，求解至少要经过多少门可到达宝藏。
解题思路：枚举所有的点的中点作为起点，宝藏作为中点，枚举所有的直线，看有多少条直线在两点之间，最后得出最少的直线的条数即可，最后备忘
了加1，因为矩形的边也算一个。
Source Code
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#define esp 1e-10
#define PI 3.1415926
using namespace std;
struct point{
double x,y;
}p[80];
point pp[80];
int cmp(const void *a,const void *b){
if(fabs(atan2((*(point *)a).y,(*(point *)a).x)-atan2((*(point *)b).y,(*(point *)b).x))<esp){
if(fabs(((*(point *)b).x)-((*(point *)a).x))<esp)return ((*(point *)b).y)-((*(point *)a).y);//x相同的按y由大到小排
if(fabs(((*(point *)b).y)-((*(point *)a).y))<esp)return ((*(point *)a).x)-((*(point *)b).x);//y相同的按x有小到大排
return atan2((*(point *)a).y,(*(point *)a).x)-atan2((*(point *)b).y,(*(point *)b).x);
}
return atan2((*(point *)a).y,(*(point *)a).x)*180/PI-atan2((*(point *)b).y,(*(point *)b).x)*180/PI;
}//按角度排序
double xmult(point p1,point p3,point p4){
return (p4.x-p3.x)*(p1.y-p3.y)-(p1.x-p3.x)*(p4.y-p3.y);
}
bool Oneside(point s,point t,point l1,point l2){
return xmult(s,l1,l2)*xmult(t,l1,l2)>esp;
}
int main()
{
int n;
cin>>n;
int i,j;
point s;
for(i=0;i<2*n;i=i+2)cin>>p[i].x>>p[i].y>>p[i+1].x>>p[i+1].y;
cin>>s.x>>s.y;
p[2*n].x=0;
p[2*n].y=0;
p[2*n+1].x=0;
p[2*n+1].y=100;
p[2*n+2].x=100;
p[2*n+2].y=0;
p[2*n+3].x=100;
p[2*n+3].y=100;
memmove(pp,p,sizeof(pp));
qsort(p,2*n+4,sizeof(point),cmp);
int min=10000;
for(i=0;i<2*n+4;i++){
point t;
int ans=0;
t.x=(p[i].x+p[(i+1)%(2*n+4)].x)/2;//这里取余让它回到第一个点
t.y=(p[i].y+p[(i+1)%(2*n+4)].y)/2;
for(j=0;j<2*n;j=j+2){
if(!Oneside(s,t,pp[j],pp[j+1]))ans++;
}
if(ans<min)min=ans;
}
cout<<"Number of doors = "<<min+1<<endl;
return 0;
}