1107 경사 율 이 0 보다 작은 연결선 수량

1107 경사 율 이 0 보다 작은 연결선 수량
기준 시간 제한: 1 초 공간 제한: 131072 KB 점수: 40 난이도: 4 레벨 알고리즘 문제
수장 하 다
관심 을 가지다
2 차원 평면 상 N 개 점 사이 에는 모두 C (n, 2) 개의 연결선 이 있다.이 C (n, 2) 개의 선 중 경사 율 이 0 보다 작은 선의 수량 을 구하 십시오.
2 차원 평면 상의 한 점 은 대응 하 는 X Y 좌표 에 따라 (X, Y) 로 표시 할 수 있다.예 를 들 어 (2, 3) (3, 4) (1, 5) (4, 6), 그 중에서 (1, 5) 와 (2, 3) (3, 4) 의 연결선 기울 임 률 이 0 이 므 로 기울 임 률 이 0 보다 적은 연결선 수량 은 2 이다.
Input

 1 ：1  N，N     (0 <= N <= 50000)
 2 - N + 1 ：N     ，     。(0 <= X[i], Y[i] <= 10^9)

Output

      0      。(2,3) (2,4)  (2,3) (3,3) 2        。

입력 예제

4
2 3
3 4
1 5
4 6

출력 예제

2

/* ***********************************************
Author        :xdlove
Created Time  :2016 05 05      20 59 59 
File Name     :2016_05_05_51nod_1391.cpp
 ************************************************ */

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>

using namespace std;
const int N = 5e4 + 5;
vector<int> vec;
int c[N << 1];

struct Node
{
    int x,y;
    void read()
    {
        scanf("%d %d",&x,&y);
    }
    void make_id()
    {
        x = get_id(x);
        y = get_id(y);
    }
    int get_id(int x)
    {
        return lower_bound(vec.begin(),vec.end(),x) - vec.begin() + 1;
    }
    bool operator < (const Node &a) const 
    {
        if(x != a.x) return x < a.x;
        return y < a.y;
    }
}p[N];

void add(int x,int n)
{
    while(x <= n)
    {
        c[x]++;
        x += x & -x;
    }
}

int get_sum(int x,int n)
{
    int s = 0;
    while(x > 0)
    {
        s += c[x];
        x -= x & -x;
    }
    return s;
}

void solve()
{
    int n; 
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        p[i].read();
        vec.push_back(p[i].x);
        vec.push_back(p[i].y);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i = 0; i < n; ++i) p[i].make_id();
    sort(p,p + n);
    int ans = 0;
    for(int i = 0; i < n; ++i)
    {
        int tp = get_sum(p[i].y,vec.size());
        ans += i - tp;
        add(p[i].y,vec.size());
    }
    cout << ans << endl;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}