竹園論壇

標題: 2318 - TOYS [打印本頁]

作者: ForTest    時間: 2014-4-30 08:07
標題: 2318 - TOYS
題目:http://poj.org/problem?id=2318
AC Code:http://ideone.com/gvN0dV

寒訓計算幾何題(說明待補)

Submission id:12499327 Status:AC
http://poj.org/status?result=0&user_id=Lucifer1998
#include <cstdio>
  • #include <cstring>

  • using namespace std;

  • struct data{
  •         double x,y;
  •         data(){}
  •         data(int _x,int _y): x(_x),y(_y){}
  •         data operator-(data a)const{return data(x - a.x , y - a.y);}
  •         data operator+(data a)const{return data(x + a.x , y + a.y);}
  •         bool operator^(data a)const{return x * a.y - y * a.x > 0;}
  • };

  • int n,m,lx,ly,rx,ry;
  • data d[7000];
  • int a[7000],b[7000],ans[7000];

  • int lower(data ask){
  •         int l = 0,r = n+1,mid;
  •         while(r - l >1){
  •                 mid  = (l+r)/2;
  •                 if(d[mid] ^ data(ask.x - b[mid], ask.y - ry))r = mid;
  •                 else l = mid;
  •         }
  •         return r;
  • }

  • int main(){
  •         while(~scanf("%d",&n),n){
  •                 scanf("%d%d%d%d%d",&m,&lx,&ly,&rx,&ry);
  •                 for(int i= 1;i<=n;++i){
  •                         scanf("%d%d",&a[i],&b[i]);
  •                         d[i] = data(a[i] - b[i] , ly - ry);
  •                 }
  •                 a[0] = b[0] = lx;
  •                 d[0] = data(0,ly-ry);
  •                 a[n+1] = b[n+1] = rx;
  •                 d[n+1] = data (0,ly - ry);
  •                 memset(ans,0,sizeof ans);
  •                 for(int i=0;i<m;++i){
  •                         int x,y;
  •                         scanf("%d%d",&x,&y);
  •                         ans[lower(data(x,y))]++;
  •                 }
  •                 for(int i=1;i<=n+1;++i){
  •                         printf("%d: %d\n",i-1,ans[i]);
  •                 }
  •                 puts("");
  •         }
  • }







  • 歡迎光臨 竹園論壇 (http://forum.tfcis.org/) Powered by Discuz! X3.2