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

why TLE?

Posted by new_star at 2008-07-20 15:58:22 on Problem 2780
//rt
#include<cstdio>

const double OO = 100000000000;
struct lineNode{
	double s;	//斜率
	int n;		//直线上总点数
} line[1005][1005];
int pNum, p, k, point[1005][2], maxn;

int main( void )
{
	while ( scanf( "%d", &pNum ) != EOF ){
		for ( p = 0; p < pNum; p++){
			scanf( "%d%d", &point[p][0], &point[p][1] );
			for ( int i = 0; i < p; i++ ){
				double s;
				if ( point[i][0] == point[p][0] ){
					s = OO;
				}
				else{
					s = 1.0*(point[i][1]-point[p][1])/(point[i][0]-point[p][0]);
				}
				k = 0;
				while ( line[i][k].n ){
					if ( s == line[i][k].s ){	//寻找经过i点斜率为s的直线
						line[i][k].n++;
						break;
					}
					k++;
				}
				if ( line[i][k].n == 0 ){	//新的直线
					line[i][k].n = 2;
					line[i][k].s = s;
				}
			}
		}
		maxn = 0;
		for ( p = 0; p < pNum; p++ ){
			k = 0;
			while ( line[p][k].n ){
				if ( line[p][k].n > maxn ) maxn = line[p][k].n;
				line[p][k].n = 0;	//为下次初始化
				line[p][k].s = 0;   //为下次初始化
				k++;
			}
		}
		printf( "%d\n", maxn );
	}
	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