网易互娱2017实习生招聘在线笔试第一场-3划线

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描写叙述

小王近期在开发一种新的游戏引擎，可是近期遇到了性能瓶颈。于是他打算从最主要的画线功能開始分析优化。

画线事实上就是调用一次drawline命令。依据给出的两端坐标，在屏幕画出相应的线段。可是小王发现，非常多的drawline事实上能够合并在一起，譬例如以下图中的线段(2,3)-(4,5)和线段(3,4)-(6,7)，事实上能够合并为一次drawline命令，直接画出线段(2,3)-(6,7)。

当然有些线段是无法合并的，如线段(-3,8)-(1,8)和线段(3,8)-(6,8)。就必须调用两次drawline命令。

画线示意图。注意颜色仅仅是用于区分。实际线段都是黑色

给出N条drawline指令以及相应的线段坐标，小王想知道，实际最少用多少次drawline指令就能够画出来。

小王想先从最简单的情况開始分析优化，所以线段仅仅包括四种情况：水平线段，垂直线段以及正反45度的线段。

输入

每一个输入数据包括多个測试点。

第一行为測试点的个数 S ≤ 10。

之后是 S 个測试点的数据。

每一个測试点的第一行为 N(N ≤ 105)。

之后是 N 行，每行包括4个整数:x0, y0, x1, y1，表示线段(x0,y0)-(x1,y1)，坐标的范围在[-108, 108]。保证线段的长度大于0。

输出

对于每一个測试点，相应的结果输出一行，表示最少用多少次指令就可以完毕全部的画线。

例子输入

2
4
3 8 6 8
-3 8 1 8
2 3 4 5
3 4 6 7
5
1 1 2 2
2 2 3 3
3 3 4 2
4 2 5 1
1 0 100 0

例子输出

3
3

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


int main()
{
    int num;
    int count,k;
    int i,j;
    long **pos;
    int x1,x2,y1,y2;
    int a1,b1,a2,b2;

    scanf("%d",&num);
    while(num--){
        scanf("%d",&k);
        count = k;

        //initize
        pos=(long**)malloc(k*sizeof(long*));
        for(i=0;i<k;i++){
            pos[i]=(long*)malloc(sizeof(long)*7);
        }
        for(i=0;i<k;i++){
            for(j=0;j<7;j++)
                pos[i][j]=37;
        }

        //input
        for(i=0;i<k;i++){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            pos[i][0] = x1;
            pos[i][1] = y1;
            pos[i][2] = x2;
            pos[i][3] = y2;

            if(x1==x2){
                pos[i][6] = x1;
            }
            else{
                pos[i][4] = (y1-y2) / (x1-x2);
                pos[i][5] = y1 - pos[i][4]*x1;
            }
        }

        //deal
        for(i=0;i<k;i++){
            for(j=i+1;j<k;j++){
                //斜率不存在情况
                a1 = pos[i][4];
                b1 = pos[i][5];
                a2 = pos[j][4];
                b2 = pos[j][5];

                if(a1==a2 && a1==37){
                    if(pos[i][3]>=pos[j][1] && pos[j][3]>=pos[i][1])
                        count--;
                }
                else if(a1==a2 && b1==b2 && pos[i][6]==37){
                    if(pos[i][2]>=pos[j][0] && pos[j][2]>=pos[i][0])
                        count--;
                }
            }
        }
        printf("%d
",count);

        //free
        for(i=0;i<k;i++)
            free(pos[i]);
        free(pos);
    }

    return 0;
}