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 |
暴力也过了~~1400ms,贴个代码参考。。。#include<iostream> #include<string.h> #include<algorithm> #include<cmath> using namespace std; int cnt[5010]; struct Node { double x; double y; }toy[5001],up[5001],down[5001]; double mult(Node a,Node b,Node c) { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } int cmp(const Node a,const Node b) { return a.x<b.x; } int main() { int n,m,i,j; double u,l,x1,x2,y1,y2,tmp1,tmp2; while(~scanf("%d",&n)&&n) { scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2); memset(cnt,0,sizeof(cnt)); up[0].x=x1; up[0].y=y1; down[0].x=x1; down[0].y=y2; up[n+1].x=x2; up[n+1].y=y1; down[n+1].x=x2; down[n+1].y=y2; for(i=1;i<=n;i++) { scanf("%lf%lf",&u,&l); up[i].x=u; up[i].y=y1; down[i].x=l; down[i].y=y2; } for(i=0;i<m;i++) scanf("%lf%lf",&toy[i].x,&toy[i].y); // sort(toy+1,toy+n+1,cmp); 这里加上就超时了 for(i=0;i<m;i++) for(j=1;j<=n+1;j++) { tmp1=mult(up[j-1],down[j-1],toy[i]); tmp2=mult(up[j],down[j],toy[i]); if(tmp1*tmp2<=0) { cnt[j-1]++; continue; } } for(i=0;i<=n;i++) printf("%d: %d\n",i,cnt[i]); printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator