| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
why TLE?//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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator