POJ 2318 2398 计算几何-白红宇

POJ 2318 2398 计算几何

阅读量：5021 次

发布时间：2019-06-12

本文共 2366 字，大约阅读时间需要 7 分钟。

POJ 2318题意:

有一个大箱子，由n个板分为n+1块，标号为0~n

已知盒子左上角和右下角的坐标及每个板上下两端的横坐标（板不会交错，且按顺序给出）

然后给出玩具的坐标，统计每块空间内玩具个数（保证玩具一定落在空间内，且没有落在隔板上的点）

题解：

二分位置，叉积判断在左侧还是右侧

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 #define N 10000 8  9 using namespace std;10 11 struct P12 {13     int x,y;14 }b[N],c[N];15 16 int n,m,sx,sy,tx,ty;17 int up[N],low[N],sw[N],sq[N];18 int ans[N];19 20 inline void read()21 {22     scanf("%d%d%d%d%d",&m,&sx,&ty,&tx,&sy);23     for(int i=1;i<=n;i++) scanf("%d%d",&up[i],&low[i]);24     for(int i=1;i<=m;i++) scanf("%d%d",&sw[i],&sq[i]);25     low[0]=up[0]=sx; low[n+1]=up[n+1]=tx;26 }27 28 inline int cross(int ax,int ay,int bx,int by)29 {30     return ax*by-ay*bx;31 }32 33 inline int getnum(int i)34 {35     int l=1,r=n+1;36     while(l<=r)37     {38         int j=(l+r)>>1;39         if(cross(up[j]-low[j],ty-sy,sw[i]-low[j],sq[i]-sy)>0) r=j-1;40         else l=j+1;41     }42     return r;43 }44 45 inline void go()46 {47     memset(ans,0,sizeof ans);48     for(int i=1;i<=m;i++)49     {50         int num=getnum(i);51         ans[num]++;52     }53     for(int i=0;i<=n;i++) printf("%d: %d\n",i,ans[i]);54     puts("");55 }56 57 int main()58 {59     while(scanf("%d",&n),n) read(),go();60     return 0;61 }

POJ 2398题意同上

唯一不同的是隔板没有按顺序给出，人工排序即可~

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 #define N 10000 8  9 using namespace std;10 11 struct P12 {13     int up,low;14 }b[N];15 16 int n,m,sx,sy,tx,ty;17 int up[N],low[N],sw[N],sq[N];18 int ans[N],ss[N];19 20 inline bool cmp(const P &a,const P &b)21 {22     return a.up
           
            >1;45 if(cross(b[j].up-b[j].low,ty-sy,sw[i]-b[j].low,sq[i]-sy)>0) r=j-1;46 else l=j+1;47 }48 return r;49 }50 51 inline void go()52 {53 memset(ans,0,sizeof ans);54 memset(ss,0,sizeof ss);55 for(int i=1;i<=m;i++)56 {57 int num=getnum(i);58 ans[num]++;59 }60 puts("Box");61 for(int i=0;i<=n;i++) ss[ans[i]]++;62 for(int i=1;i<=n;i++)63 if(ss[i]) printf("%d: %d\n",i,ss[i]);64 }65 66 int main()67 {68 while(scanf("%d",&n),n) read(),go();69 return 0;70 }