计算几何在程序设计竞赛中的应用知识课件.ppt

计算几何在程序设计竞赛中的应用预备知识(I)预备知识(II)预备知识(VI)预备知识(V)基本问题举例(Ⅰ)基本问题举例(Ⅰ)基本问题举例(Ⅰ)基本问题举例（Ⅱ）基本问题举例（Ⅱ）基本问题举例（Ⅱ）基本问题举例（Ⅱ）基本问题举例（Ⅱ）基本问题举例（Ⅱ）intmain(intargc,char*argv[]){
//…
intpartion_num=line_on_edge(cuttings[0])?1:2;
for(inti=1;i<line_num;i++){
if(line_on_edge(cuttings[i]))continue;
vector<fpoint>new_cross_pts;
for(intj=0;j<i;j++){
fpointcross_pt;
if(cacu_cross_point(cuttings[i],cuttings[j],cross_pt)>0
&&!point_already_exists(cross_pt,new_cross_pts)){
new_cross_pts.push_back(cross_pt);
}
}
partion_num+=(1+new_cross_pts.size());
}
cout<<partion_num<<endl;
}

return0;
}基本问题举例(Ⅲ)基本问题举例(Ⅲ)基本问题举例(Ⅳ)基本问题举例(Ⅳ)基本问题举例(Ⅳ)基本问题举例(Ⅳ)附加问题(需要离散化问题)附加问题(需要离散化问题)附加问题(需要离散化问题)附加问题(需要离散化问题)附加问题(需要离散化问题)附加问题(需要离散化问题)附加问题(需要离散化问题)附加问题(需要离散化问题)