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

## Re:sort+折半查找终于过了，附代码！

Posted by PoorGuy at 2017-05-04 00:13:03 on Problem 2785
In Reply To:sort+折半查找终于过了，附代码！ Posted by:201501060326 at 2016-02-23 17:31:42
```> #include <stdio.h>
> #include <algorithm>
> #include <stdlib.h>
> using namespace std;
> int num[5000][4];
> int x[160000000];
> int y[160000000];
> int find(int a[],int m,int n)
> {
>     int left,right,middle,pd=0,ans=0;
>     left=0;
>     right=m-1;
>     while(left<=right)
>     {
>         middle=(left+right)>>1;
>         if(a[middle]==n)
>         {
>             pd=1;
>             break;
>         }
>         else if(a[middle]<n)
>         {
>             left=middle+1;
>         }
>         else
>         {
>             right=middle-1;
>         }
>     }
>     if(pd==1)
>     {
>         for(ans=0; left<m; left++)
>         {
>             if(a[left]==n)
>             {
>                 ans++;
>             }
>             else if(ans!=0&&a[left]!=n)
>             {
>                 break;
>             }
>         }
>         return ans;
>     }
>     return -1;
> }
> int main()
> {
>     int i,j,n,ans,count,temp;
>     while(scanf("%d",&n)!=EOF)
>     {
>         for(i=0; i<n; i++)
>         {
>             for(j=0; j<4; j++)
>             {
>                 scanf("%d",&num[i][j]);
>             }
>         }
>         for(i=0,count=0; i<n; i++)
>         {
>             for(j=0; j<n; j++)
>             {
>                 x[count]=num[i][0]+num[j][1];
>                 y[count++]=num[i][2]+num[j][3];
>             }
>         }
>         sort(x,x+count);
>         sort(y,y+count);
>         for(i=0,ans=0; i<count; i++)
>         {
>             temp=find(x,count,-y[i]);
>             if(temp!=-1)
>             {
>                 ans+=temp;
>             }
>         }
>         printf("%d\n",ans);
>     }
>     return 0;
> }
```

Followed by: