Problem
Chef is working with lines on a 2-D plane.
He knows that every line on a plane can be clearly defined by three coefficients A, B and C: any point (x, y) lies on the line if and only if A * x + B * y + C = 0.
Let's call a set of lines to be perfect if there does not exist a point that belongs to two or more distinct lines of the set.
He has a set of lines on a plane and he wants to find out the size of the largest perfect subset of this set.
Input
The first line of input contains one integers T denoting the number of test cases.
Each test case consists of one integer N denoting number of lines.
Next N lines contain 3 space-separated integers each denoting coefficients A, B and C respectively.
Output
For each test case output the cardinality of the largest perfect subset in a single line.
Constraints
- 1 ≤ N ≤ Nmax
- Sum over all N for all test cases ≤ NSmax
- |A|, |B|, |C| ≤ 109
- For a line with coefficients A, B and C either A or B is not zero.
Subtasks
- Subtask #1 [35 points]: Nmax = 5000, NSmax = 50000
- Subtask #2 [65 points]: Nmax = NSmax = 105
Sample 1:
1 5 1 0 0 1 2 3 3 4 5 30 40 0 30 40 50
2
Explanation:
Lines 3*x + 4*y + 5 = 0 and 30*x + 40*y + 0 = 0 form a biggest perfect subset.
Program :
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#define max(a,b) a>b?a:b
int gcd(int p, int q) {
if(q == 0)
return p;
else
return gcd(q,p%q);
}
int compare(const void *r, const void *s) {
double *p, *q;
p = (double *)r;
q = (double *)s;
if(p[0] > q[0])
return 1;
else if(p[0] < q[0])
return -1;
else {
if(p[1]>q[1])
return 1;
else if(q[1] > p[1])
return -1;
}
return 0;
}
int main() {
int t, n, ans, i, count,a,b,c;
double le[100005][2];
scanf("%d",&t);
while(t--) {
ans = 0;
scanf("%d",&n);
for(i = 0; i < n; i++) {
scanf("%d%d%d",&a,&b,&c);
if(b) {
le[i][0] = (double)a/b;
if(a)
le[i][1] = (double)c/gcd(a,b);
else
le[i][1] = (double)c/b;
}
else {
le[i][0] = INT_MIN;
le[i][1] = (double)c/a;
}
}
qsort(le,n,sizeof(double)*2,compare);
count = 1;
for(i = 1;i < n; i++) {
if(le[i][0] == le[i-1][0] ) {
if(le[i][1] != le[i-1][1])
count++;
}
else {
ans = max(ans,count);
count = 1;
}
}
ans = max(ans,count);
printf("%d\n",ans);
}
return 0;
}
0 Comments