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

离散化300MS水过。。

Posted by ff_666 at 2018-03-17 10:16:15 on Problem 2002
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=2e4,B=4e4;
int n,ans,num[40005],tep[2005];bool vis[2005][2005];
struct ff{
	int x,y;
}a[1005];
int read(){
	int ret=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return f?-ret:ret;
}
void make(){
	sort(tep+1,tep+1+tep[0]);
	num[tep[1]]=1;
	for(int i=2;i<=tep[0];i++) num[tep[i]]=num[tep[i-1]]+(tep[i]!=tep[i-1]);
	for(int i=1;i<=n;i++) vis[num[a[i].x]][num[a[i].y]]=1;
}
bool check(int x,int y){return (0<=x&&x<=B&&0<=y&&y<=B&&vis[num[x]][num[y]]);}
int main(){
	int x,y,x_,y_,La,Lb;
	for(n=read();n;n=read()){
		tep[0]=0;
		for(int i=1;i<=n;i++) tep[++tep[0]]=a[i].x=read()+M,tep[++tep[0]]=a[i].y=read()+M;
		make();ans=0;
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)if(i!=j){
		  	La=a[i].x-a[j].x,Lb=a[i].y-a[j].y;
		  	x=a[i].x+Lb,y=a[i].y-La,x_=a[j].x+Lb,y_=a[j].y-La;
		  	if(check(x,y)&&check(x_,y_)) ans++;
		  }
		for(int i=1;i<=n;i++) vis[num[a[i].x]][num[a[i].y]]=0;
		printf("%d\n",ans>>2);
	}
	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