[CF 1163C2] Power Transmission (Hard Edition)

[CF 1163C2] Power Transmission (Hard Edition) - 2000

문제 설명 : 

풀이 :

주의할 점 : 

배울 점 : 

2차원 좌표평면 상의 직선을 표현하기 위해서는 일반적으로 기울기와 y절편이 필요하다. 그런데 기울기나 y절편 모두 정수가 아닌 유리수 형태일 수도 있다. c++에서는 소수의 정밀도 문제 때문에 유리수를 그대로 사용하는 것은 위험하다. 따라서 이런 경우에는 일반적으로 두 정수로 표현되는 기약분수 꼴로 나타낸다. 여기서 나는 기울기와 y절편 모두 유리수가 될 수 있으므로 (기울기의 분모,기울기의 분자, y절편의 분모, y절편의 분자) 총 4개의 dimension이 필요할 것 같아서 너무 복잡하다고 생각했다. 그런데 사실 일차함수에서는 단 3개면 된다. 

우리가 일반적으로 알고있는 y=ax+b형태에서 기울기 a는 (y1-y2) / (x1-x2)로 표현된다. 이를 대입해보면 y=(y1-y2)/(x1-x2)*x+b이고 이항해서 정리하면 (x2-x1)y-*(y2-y1)x=b형태가 된다. 즉 b를 굳이 유리수 형태가 아닌 정수 형태로 표현이 가능하다는 것이다. 따라서 단 3개의dimension으로 모든 일차함수 형태를 표현할 수 있는 것이다. 이때의 b를 c라고 하자. 그러면 dx(=x1-x2),dy(y1-y2),c의 gcd1를 구해서 각자 모두 나눠서 서로소 꼴로 만들어준다. 그 3개의 값을 하나로 묶어서 set에다가 insert하는 것이다. 그리고 기울기는 같지만 c값이 다른 직선들도 별도로 카운트해야하므로 이번에는 dx,dy만의 gcd2를 구해서 나눠준 다음 이 값을 map<pair<int,int>,int>에 넣어준다.

최종적으로 정답은 set에 들어있는 원소의 수=m, map의 각 기울기 별 원소의 수를 k_i라고 했을 때 "mC2 - sum of (k_iC2) on every i" 이다.

이번에 처음으로 tuple헤더를 써 보았다. tuple은 pair의 확장으로 생각하면 된다. pair는 멤버를 단 두개밖에 넣지 못했지만 tuple같은 경우는 3개 이상도 넣을 수 있다. 사용하는 방법도 pair를 쓸 때처럼 {}안에다가 원소를 넣어주면 된다. tuple을 사용하게 되면 3개 이상의 수를 비교해야 할 때, 기존에는 min(min(a,b,),c)처럼 min안에 min을 넣어야 했지만 tuple을 사용하면 min({a,b,c})이렇게 적기만 해도 되어서 간단하다.

코드:

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
#include<tuple>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 1009;
 
int x[SIZE],y[SIZE];
 
int getGCD(int a,int b){
    return (b==0)?a:getGCD(b,a%b);
}
 
int main(){
    int n;  scanf("%d",&n);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d %d",&x[i],&y[i]);
    }
 
    map<pii,int> mp;
    set<tuple<int,int,int>> st;
 
    for(int i=1 ; i<=n ; i++){
        for(int j=i+1 ; j<=n ; j++){
            int dx=x[i]-x[j],dy=y[i]-y[j];
            int c=dx*y[i]-dy*x[i];
 
            int gcd1=getGCD(dx,dy);
            int gcd2=getGCD(getGCD(dx,dy),c);
 
            printf("%d %d %d %d\n",dx,dy,c,gcd2);
            if(st.count({dx/gcd2,dy/gcd2,c/gcd2})) continue;
            st.insert({dx/gcd2,dy/gcd2,c/gcd2});
            mp[{dx/gcd1,dy/gcd1}]++;
        }
    }
 
    ll m=st.size();
    ll ans=m*(m-1)/2;
 
    for(auto &here:mp){
        int sec=here.second;
        ans-=1LL*sec*(sec-1)/2;
    }
 
    printf("%lld\n",ans);
 
    return 0;
}
/*

*/