小L的直线

小学时期的小L发现自己很有艺术细胞，于是买了一块画板，但是他的绘画水平使得他只能连接两点画出一条线段。有一天他决定在一张有n个点的图上作画，即他可以把这n个点任意连接。大家认为平行线是非常不美观的，于是他想知道自己最多能画多少条直线使整张画不出现平行线。

输入

第一行输入一个整数n （1 <= n <= 200）
接下来n行每行两个整数代表每个点的坐标x, y （-1000 <= x, y <= 1000）

输出

一行一个整数为能画出最多的两两不平行的直线条数

样例输入 Copy

样例输出 Copy

4
关于平行线的题目以前做过，但是没想起来
求平行线的方法：用一个map存储当前两个点的“斜率”（只需要存储x和y的差值），然后取反在存一次（因为x,y和-x,-y不相等但是平行，所以我们要存两遍， ）然后遍历map的每一个斜率可以根据a*(a-1)/2来计算相等的个数，然后在累加，最后再除以2（别忘了我们斜率存了两次）
本题目题解：本题中我们要先求平乡线，但我们只要保存相同斜率的个数，（不用取反，就存一次），然后斜率相同的我们只要1个也就是总个数减去某个斜率的总数，然后加1就行了

#include<iostream>

#include<map>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long ll;

pair<int ,int>p;

vector<pair<int,int> >ve;

map<pair<int ,int >,int>mp;//保存斜率与斜率出现的次数

map<ll,int >mp1;

map<pair<int ,int >,int>::iterator it;

int main(){

    int n;

    int sum=;

    cin>>n;

    for(int i=;i<n;i++){

        cin>>p.first>>p.second;

        ve.push_back(p);//用vector保存给的数据

    }

    int x1,a,b,x2;

    for(int i=;i<n;i++){

        for(int j=i+;j<n;j++){

            a=ve[i].second-ve[j].second;

            b=ve[i].first-ve[j].first;

            x1=__gcd(a,b);

            a=a/x1;

            b=b/x1;

            p.first=b;

            p.second=a;

            mp[p]++;

//            p.first=-b;

//            p.second=-a;

//            mp[p]++;

        }

    }

    int ans=;

    int s=n*(n-)/;

    for(it=mp.begin();it!=mp.end();it++){

        s=s-it->second+;

    }

    cout<<s<<endl;

    return ;

}

巴特西

小L的直线

最新文章

热门文章