Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

暴力也过了~~1400ms,贴个代码参考。。。

Posted by crazy852456 at 2012-08-15 14:53:36 on Problem 2318
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator