Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
二分?我感觉就是一暴力水题266ms路过。#include <iostream> #include <cstdio> #include <vector> #include <cstring> using namespace std; class Line{ public: int lt,up,rt,dn; Line(){}; Line(int l,int u,int r,int d){ this->lt=l; this->up=u; this->rt=r; this->dn=d; } void set(int l,int u,int r,int d){ this->lt=l; this->up=u; this->rt=r; this->dn=d; } bool side(int x,int y){ return (x-lt)*(up-dn)>(y-up)*(lt-rt); } }; int res[5555]; int main() { int n,m,lt,up,rt,dn,ltmp,rtmp;//box lt:left,rt:right, dn:down,ltmp:left tmp,rtmp:right tmp int i,j; //for circle int x,y; //toy.x,toy.y vector<Line> v; bool first=1; while(scanf("%d",&n)&&n){ if(first){ first=0; }else{ puts(""); } scanf("%d%d%d%d%d",&m,<,&up,&rt,&dn); v.clear(); v.resize(n+1); memset(res,0,sizeof(res)); for(i=0;i<n;i++){ scanf("%d%d",<mp,&rtmp); v[i].set(ltmp,up,rtmp,dn); } v[n].set(rt,up,rt,dn); for(i=0;i<m;i++){ scanf("%d%d",&x,&y); for(j=0;j<=n;j++){ if(!v[j].side(x,y)){ res[j]++; break; } } } for( i=0;i<=n;i++){ printf("%d: %d\n",i,res[i]); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator