注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2398 Toy Storage 叉乘  

2011-04-14 21:24:35|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://poj.org/problem?id=2398
poj2318的翻版,所不同的是本题所给的线并不排好序的,加一个sort()函数排序即可。(poj2318解题报告

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
double y1,y2,**p=new double*[1005];
double judge(int j,double x,double  y)
{
        return (p[j][1]-p[j][0])*(y-y1)-(y2-y1)*(x-p[j][0]);
}
bool cmp(double *a,double *b)
{
        return  a[0]<b[0];
}     
int main()
{
        int ans[1005],ans2[1005],i,j,n,m,low,high,mid;
        double x,y,x1,x2;
        while(scanf("%d",&n),n)
        {
                memset(ans,0,sizeof(ans));
                memset(ans2,0,sizeof(ans2));
                scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
                for(i=1;i<=n;i++)
                {
                        p[i]=new double[2];
                        scanf("%lf%lf",&p[i][0],&p[i][1]);
                }
                p[0]=new double[2];p[n+1]=new double[2];
                p[0][0]=x1;p[0][1]=x1;
                p[n+1][0]=x2;p[n+1][1]=x2;
                sort(p+1,p+n+1,cmp);
                for(i=0;i<m;i++)
                {
                        low=0;high=n+1;
                        mid=(low+high)/2;
                        scanf("%lf%lf",&x,&y);
                        if(judge(0,x,y)==0)
                                mid=0;
                        else if(judge(n+1,x,y)==0)
                                mid=n;
                        else
                        {
                                while(low<high)
                                {
                                        if(judge(mid,x,y)<0)
                                        {
                                                high=mid-1;
                                                mid=(low+high)/2;
                                        }
                                        else
                                        {
                                                low=mid+1;
                                                mid=(low+high)/2;
                                        }
                                }
                                if(judge(mid,x,y)<0)
                                        mid--;
                        }
                        ans[mid]++;
                }
                for(i=0;i<=n;i++)
                        ans2[ans[i]]++;
                printf("Box\n");
                for(i=1;i<=m;i++)
                        if(ans2[i])
                                printf("%d: %d\n",i,ans2[i]);
               
        }
        return 0;
}
  评论这张
 
阅读(97)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018