That Nice Euler Circuit & What's your Logo?

xiaoB.M. 发表于 2007-08-28 00:09:17

That Nice Euler Circuit& What's your Logo? 是HOJ上的2个类似的题目,题目大意就是给出一些连续线段问总共组成了多少个面。解法就是求线段的交点数,好像有个定理的吧。规则就是线段的起点不能算作交点。处理线段共线的时候要注意一下,其他地方没什么,贴下模板就可以了。

下面是That Nice Euler Circuit 的 主函数:

Point p[MAX_N];
Line l[MAX_N];
Point pp[MAX_N];
int n,nP;

int main()
{
    int i,j,tmp;
    int ans,Case;
    Case = 1;
    while(scanf("%d",&n),n)
    {
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        //p[n] = p[0];
        for(i=0;i<n-1;i++)
        {
            l[i].p1 = p[i];
            l[i].p2 = p[i+1];
        }
        ans = 0;
        for(i=0;i<n-1;i++)
        {
            nP = 0;
            for(j=0;j<i;j++)
            {
                if(LineSegIntersect(l[i],l[j]))
                {
                    Point tmpP;
                    if(CalCrossPoint(l[i],l[j],tmpP)==COLINE)
                    {
                        if(l[i].p1 == l[j].p2 || l[i].p1 == l[j].p1) continue;
                        else tmpP = l[i].p2;
                    }
                    if(tmpP == l[i].p1) continue;
                    pp[nP++] = tmpP;
                }
            }
            sort(pp,pp+nP,cmp);
            ans += nP;
            for(j=1;j<nP;j++)
            {
                if(pp[j] == pp[j-1])
                {
                    ans--;
                }
            }
        }
        printf("Case %d: There are %d pieces.\n",Case++,ans+1);
    }
    return 0;
}

关键词(Tag): acm 计算几何

收藏: QQ书签 del.icio.us 订阅: Google 抓虾

最新评论

发表评论

* 昵称

已经注册过? 请登录

新用户请先注册 以便能显示头像及追踪评论回复

Email
网址
* 评论
表情
 
 

分类小组论坛
杂谈, 娱乐、八卦, 文学、艺术, 体育, 旅游、同城, 象牙塔, 情感, 时尚、生活, 星座, 科技

请注意遵守中华人民共和国法律法规, 如威胁到本站生存, 将依法向有关部门报告, 同时本站的相关记录可能成为对您不利的证据.

相关法律法规
全国人大常委会关于维护互联网安全的决定
中华人民共和国计算机信息系统安全保护条例
中华人民共和国计算机信息网络国际联网管理暂行规定
计算机信息网络国际联网安全保护管理办法
计算机信息系统国际联网保密管理规定