Transmit

gistfile1.c

/* 
 * File:   transmit.c
 * Author: Vojta
 *
 * Created on December 14, 2011, 10:05 AM
 */


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double distance(int x1, int y1, int x2, int y2){
    return sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

int cross_product(int x1, int y1, int x2, int y2){
    return x1*y2 - x2*y1;
}

int main(int argc, char** argv) {
    int tx, ty, points, j, k, px[160], py[160], x, y, num_points;
    double radius, EPS = 1e-8;
    while (1) {
        scanf("%d %d %lf\n", &tx, &ty, &radius);
        if(radius - EPS < 0) break;
        scanf("%d\n", &points);
        num_points = 0;
        while(points--){
            scanf("%d %d\n", &x, &y);
            if (distance(tx, ty, x, y) - EPS > radius) continue;
            px[num_points] = x;
            py[num_points] = y;
            num_points++;
        }
        
        int maximum = 0, count1, count2; 
        for(j = 0; j < num_points; j++){
            count1 = 0; count2 = 0;
            for(k = 0; k < num_points; k++){
                int cp = cross_product(px[j]-tx, py[j]-ty, px[k]-tx, py[k]-ty); 
                if (cp == 0){
                    count1++; count2++;
                }else if (cp < 0){
                    count2++;
                }else if (cp > 0){
                    count1++;
                }
            }
            if (count1 > maximum) maximum = count1;
            if (count2 > maximum) maximum = count2;
        }
        printf("%d\n", maximum);
    }
    return (EXIT_SUCCESS);
}