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

简单题n^2水过

Posted by zhouzhendong at 2017-02-26 12:49:03 on Problem 3668
对于每条线段,按照斜率排序,对于横线和竖线特判即可

#include <cstdio>
#include <algorithm>
struct L{
	int dx,dy;
}line[41000];
int n,x[210],y[210],lz;
bool fx,fy;
int gcd(int x,int y){
	if (!y) return x;
	   else return gcd(y,x%y);
}
bool cmp(L a,L b){
	double x1=a.dx,x2=b.dx,y1=a.dy,y2=b.dy;
	double k1=x1/y1,k2=x2/y2;
	return k1<k2;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	lz=fx=fy=0;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++){
			lz++;
			line[lz].dx=x[j]-x[i];
			line[lz].dy=y[j]-y[i];
			if (line[lz].dx<0)
				line[lz].dx=-line[lz].dx,line[lz].dy=-line[lz].dy;
			if (!line[lz].dx||!line[lz].dy){
				lz--;
				if (!line[lz+1].dx&&!line[lz+1].dy)
					continue;
				if (!line[lz+1].dx) fx=1;
				if (!line[lz+1].dy) fy=1;
				continue;
			}
			int g=gcd(line[lz].dx,abs(line[lz].dy));
			line[lz].dx/=g;
			line[lz].dy/=g;
		}
	std::sort(line+1,line+lz+1,cmp);
	int ans=fx+fy+1;
	for (int i=2;i<=lz;i++)
		if (line[i].dx!=line[i-1].dx||line[i].dy!=line[i-1].dy)
			ans++;
	printf("%d",ans);
	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