[FOJ1904 Cake,Cake,Delicious]DFS+凸包 or DFS+半平面交

【题目链接】http://acm.fzu.edu.cn/problem.php?pid=1904
【题目大意】
师傅买了一个矩形的大蛋糕，切了N刀，问这个大蛋糕剩下的块里最大的一块有多大?
【算法分析】
首先最直接的方法：
DFS每刀的直线方程>=0还是<=0，然后求半平面交。
第二种方法：
DFS每刀的直线方程>=0还是<=0，然后再枚举所有直线的交点中在这个半平面内的。
对这些点做凸包，然后算面积。
【其它】
我是傻×。。。居然WA了一遍。
AC的：
printf("Case #%d: %.3lfn",i,ans);
WA的：
printf("Case #%d: %.3lfn",Tc,ans);
样例都不过就拿去交了= =。。。。。
【CODE】
#include #include #include #include #define AA ((Point*)A)
#define BB ((Point*)B)
const int N=30;
const double eps=1e-6;
int n,pn,plt,Lt,List[N*N];
double ans,S;
struct Line{int a,b,c;}L[N];
struct Point{double x,y;}P[N*N],pl[N*N];

void Add_Line(int i,int x1,int y1,int x2,int y2){
L[i].a=y1-y2;
L[i].b=x2-x1;
L[i].c=x1*y2-x2*y1;
}

void Add_Point(Line A,Line B){
int tmp=A.a*B.b-B.a*A.b;
if (!tmp) return;
pn++;
P[pn].x=(double)(A.b*B.c-B.b*A.c)/tmp;
P[pn].y=(double)(B.a*A.c-A.a*B.c)/tmp;
}

void input(){
scanf("%d",&n);
for (int i=0;i int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
Add_Line(i,x1,y1,x2,y2);
}
Add_Line(n,0,100,0,0);
Add_Line(n+1,0,0,100,0);
Add_Line(n+2,100,0,100,100);
Add_Line(n+3,100,100,0,100);
pn=0;
for (int i=0;i for (int j=i+1;j Add_Point(L[i],L[j]);
P[N*N-1].x=0;
P[N*N-1].y=0;
}

int cj(Point p0,Point p1,Point p2){
double res=(p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
if (fabs(res) if (res<0) return -1;
return 1;
}

bool In_Line(Point pp,Line ll){
double res=pp.x*ll.a+pp.y*ll.b+ll.c;
if (fabs(res) if (res>=0) return true;
return false;
}

void swap(Point &A,Point &B){
Point tmp=A;
A=B;
B=tmp;
}

int cmp(const void *A,const void *B){
return cj(P[N*N-1],*AA,*BB);
}

void TB(){
if (plt<3) return;
Point m;
int maxi=0;
m.x=1e50;
for (int i=1;i<=plt;i++)
if (pl[i].x m=pl[i];
maxi=i;
}
for (int i=1;i<=plt;i++){
pl[i].x-=m.x;
pl[i].y-=m.y;
}
swap(pl[1],pl[maxi]);
qsort(pl+2,plt-1,sizeof(Point),cmp);
pl[plt+1]=pl[1];
Lt=1; List[1]=1;
for (int i=2;i<=plt+1;i++){
while (Lt>1 && cj(pl[List[Lt-1]],pl[i],pl[List[Lt]])<=0) Lt--;
List[++Lt]=i;
}
}

void Count(){
S=0;
if (plt<3) return;
for (int i=1;i Point &pre=pl[List[i]],&now=pl[List[i+1]];
S+=pre.x*now.y-pre.y*now.x;
}
S=fabs(S)/2;
}

void Try(){
int i,j;
plt=0;
for (i=1;i<=pn;i++){
bool flag=true;
for (j=0;j if (!In_Line(P[i],L[j])){
flag=false;
break;
}
if (flag) pl[++plt]=P[i];
}
TB();
Count();
if (S>ans) ans=S;
}

void dfs(int depth){
if (depth==n) {Try(); return;}
dfs(depth+1);
L[depth].a=-L[depth].a;
L[depth].b=-L[depth].b;
L[depth].c=-L[depth].c;
dfs(depth+1);
L[depth].a=-L[depth].a;
L[depth].b=-L[depth].b;
L[depth].c=-L[depth].c;
}

int main(){
freopen("1904.in","r",stdin);
freopen("1904.out","w",stdout);
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
input();
ans=0;
dfs(0);
printf("Case #%d: %.3lfn",i,ans);
}
}