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

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

Posted by 201501060326 at 2016-02-23 17:31:42 on Problem 2785
```#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: