Guest User

Untitled

a guest
May 18th, 2013
259
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 12.98 KB | None | 0 0
  1. #define FileIO
  2. using System;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5. using System.Text;
  6. using System.IO;
  7. using System.Diagnostics;
  8. using System.Threading;
  9.  
  10.  
  11. namespace CF
  12. {
  13.     //delegate double F(double x);
  14.     //delegate decimal Fdec(decimal x);
  15.  
  16.     class Program
  17.     {
  18.  
  19.         static void Main(string[] args)
  20.         {
  21.  
  22. #if FileIO
  23.             StreamReader sr = new StreamReader("triangles.in");
  24.             StreamWriter sw = new StreamWriter("triangles.out");
  25.             Console.SetIn(sr);
  26.             Console.SetOut(sw);
  27. #endif
  28.  
  29.             Dictionary<int, int> xHash = new Dictionary<int, int>();
  30.             Dictionary<int, int> yHash = new Dictionary<int, int>();
  31.             int n = ReadInt();
  32.             int[] _x = new int[n];
  33.             int[] _y = new int[n];
  34.             for (int i = 0; i < n; i++)
  35.             {
  36.                 string[] input = ReadArray();
  37.                 int x = int.Parse(input[0]);
  38.                 int y = int.Parse(input[1]);
  39.                 if (xHash.ContainsKey(x))
  40.                     xHash[x]++;
  41.                 else
  42.                     xHash.Add(x, 1);
  43.                 if (yHash.ContainsKey(y))
  44.                     yHash[y]++;
  45.                 else
  46.                     yHash.Add(y, 1);
  47.                 _x[i] = x;
  48.                 _y[i] = y;
  49.             }
  50.             int[] onLine = new int[n];
  51.             for (int i = 0; i < n; i++)
  52.             {
  53.                 onLine[_x[i]] += (yHash[_y[i]] - 1);
  54.             }
  55.             long ans = 0;
  56.             foreach (int x in xHash.Keys)
  57.             {
  58.                 ans += onLine[x] * (xHash[x] - 1);
  59.             }
  60.             Console.WriteLine(ans);
  61.  
  62. #if Online
  63.             Console.ReadLine();
  64. #endif
  65.  
  66. #if FileIO
  67.             sr.Close();
  68.             sw.Close();
  69. #endif
  70.         }
  71.  
  72.         static string[] ReadArray()
  73.         {
  74.             return Console.ReadLine().Split(' ');
  75.         }
  76.  
  77.         static int ReadInt()
  78.         {
  79.             return int.Parse(Console.ReadLine());
  80.         }
  81.     }
  82.  
  83.    /* public static class MyMath
  84.     {
  85.         public static long BinPow(long a, long n, long mod)
  86.         {
  87.             long res = 1;
  88.             while (n > 0)
  89.             {
  90.                 if ((n & 1) == 1)
  91.                 {
  92.                     res = (res * a) % mod;
  93.                 }
  94.                 a = (a * a) % mod;
  95.                 n >>= 1;
  96.             }
  97.             return res;
  98.         }
  99.  
  100.         public static long GCD(long a, long b)
  101.         {
  102.             while (b != 0) b = a % (a = b);
  103.             return a;
  104.         }
  105.  
  106.         public static int GCD(int a, int b)
  107.         {
  108.             while (b != 0) b = a % (a = b);
  109.             return a;
  110.         }
  111.  
  112.         public static long LCM(long a, long b)
  113.         {
  114.             return (a * b) / GCD(a, b);
  115.         }
  116.  
  117.         public static int LCM(int a, int b)
  118.         {
  119.             return (a * b) / GCD(a, b);
  120.         }
  121.     }
  122.  
  123.     public class SegmentTree
  124.     {
  125.         int[] v_min;
  126.         int[] v_max;
  127.         int[] mas;
  128.         public void BuildTree(int[] a)
  129.         {
  130.             int n = a.Length - 1;
  131.             int z = 0;
  132.             while (n >= 2)
  133.             {
  134.                 z++;
  135.                 n >>= 1;
  136.             }
  137.             n = 1 << (z + 1);
  138.             v_min = new int[n << 1];
  139.             v_max = new int[n << 1];
  140.             mas = new int[n << 1];
  141.             for (int i = n; i < n + a.Length; i++)
  142.                 v_min[i] = a[i - n];
  143.             for (int i = n + a.Length; i < v_min.Length; i++)
  144.                 v_min[i] = int.MaxValue;
  145.             for (int i = n - 1; i > 0; i--)
  146.                 v_min[i] = Math.Min(v_min[(i << 1)], v_min[(i << 1) + 1]);
  147.  
  148.             for (int i = n; i < n + a.Length; i++)
  149.                 v_max[i] = a[i - n];
  150.             for (int i = n + a.Length; i < v_max.Length; i++)
  151.                 v_max[i] = int.MinValue;
  152.             for (int i = n - 1; i > 0; i--)
  153.                 v_max[i] = Math.Max(v_max[(i << 1)], v_max[(i << 1) + 1]);
  154.  
  155.         }
  156.         //nil
  157.         public int RMQ_MIN(int l, int r)
  158.         {
  159.             int ans = int.MaxValue;
  160.             l += v_min.Length >> 1;
  161.             r += v_min.Length >> 1;
  162.             const int o = 1;
  163.             while (l <= r)
  164.             {
  165.                 if ((l & 1) == o)
  166.                     ans = Math.Min(ans, v_min[l]);
  167.                 if (!((r & 1) == 0))
  168.                     ans = Math.Min(ans, v_min[r]);
  169.                 l = (l + 1) >> 1;
  170.                 r = (r - 1) >> 1;
  171.             }
  172.             return ans;
  173.         }
  174.  
  175.         public int RMQ_MAX(int l, int r)
  176.         {
  177.             int ans = int.MinValue;
  178.             l += v_max.Length >> 1;
  179.             r += v_max.Length >> 1;
  180.             const int o = 1;
  181.             while (l <= r)
  182.             {
  183.                 if ((l & 1) == o)
  184.                     ans = Math.Max(ans, v_max[l]);
  185.                 if (!((r & 1) == 0))
  186.                     ans = Math.Max(ans, v_max[r]);
  187.                 l = (l + 1) >> 1;
  188.                 r = (r - 1) >> 1;
  189.             }
  190.             return ans;
  191.         }
  192.  
  193.         public void Put(int l, int r, int op)
  194.         {
  195.             l += mas.Length >> 1;
  196.             r += mas.Length >> 1;
  197.             while (l <= r)
  198.             {
  199.                 if (l % 2 != 0)
  200.                     mas[l] = op;
  201.                 if (r % 2 == 0)
  202.                     mas[r] = op;
  203.                 l = (l + 1) >> 1;
  204.                 r = (r - 1) >> 1;
  205.             }
  206.         }
  207.  
  208.         public int Get(int x)
  209.         {
  210.             x += mas.Length >> 1;
  211.             int ans = int.MinValue;
  212.             while (x > 0)
  213.             {
  214.                 ans = Math.Max(mas[x], ans);
  215.                 x >>= 1;
  216.             }
  217.             return ans;
  218.         }
  219.  
  220.         public void Update(int i, int x)
  221.         {
  222.             i += v_min.Length >> 1;
  223.             v_min[i] = x;
  224.             v_max[i] = x;
  225.             i >>= 1;
  226.             while (i > 0)
  227.             {
  228.                 v_min[i] = Math.Min(v_min[(i << 1)], v_min[(i << 1) + 1]);
  229.                 v_max[i] = Math.Max(v_max[(i << 1)], v_max[(i << 1) + 1]);
  230.                 i >>= 1;
  231.             }
  232.         }
  233.     }
  234.  
  235.     class Edge
  236.     {
  237.         public int a;
  238.         public int b;
  239.         public int w;
  240.  
  241.         public Edge(int a, int b, int w)
  242.         {
  243.             this.a = a;
  244.             this.b = b;
  245.             this.w = w;
  246.         }
  247.     }
  248.  
  249.    /* class Graph
  250.     {
  251.         public List<int>[] g;
  252.         public int[] color; //0-white, 1-gray, 2-black
  253.         public int[] o; //open
  254.         public int[] c; //close
  255.         public int[] p;
  256.         public int[] d;
  257.         public List<Edge> e;
  258.  
  259.         public Graph(int n)
  260.         {
  261.             g = new List<int>[n + 1];
  262.             color = new int[n + 1];
  263.             o = new int[n + 1];
  264.             c = new int[n + 1];
  265.             p = new int[n + 1];
  266.             d = new int[n + 1];
  267.         }
  268.     }
  269.  
  270.     static class GraphUtils
  271.     {
  272.         const int white = 0;
  273.         const int gray = 1;
  274.         const int black = 2;
  275.  
  276.         public static void BFS(int s, Graph g)
  277.         {
  278.             Queue<int> q = new Queue<int>();
  279.             q.Enqueue(s);
  280.             while (q.Count != 0)
  281.             {
  282.                 int u = q.Dequeue();
  283.                 for (int i = 0; i < g.g[u].Count; i++)
  284.                 {
  285.                     int v = g.g[u][i];
  286.                     if (g.color[v] == white)
  287.                     {
  288.                         g.color[v] = gray;
  289.                         g.d[v] = g.d[u] + 1;
  290.                         g.p[v] = u;
  291.                         q.Enqueue(v);
  292.                     }
  293.                 }
  294.                 g.color[u] = black;
  295.             }
  296.         }
  297.  
  298.         public static void DFS(int u, ref int time, Graph g)
  299.         {
  300.             g.color[u] = gray;
  301.             time++;
  302.             g.o[u] = time;
  303.             for (int i = 0; i < g.g[u].Count; i++)
  304.             {
  305.                 int v = g.g[u][i];
  306.                 if (g.color[v] == white)
  307.                 {
  308.                     g.p[v] = u;
  309.                     DFS(v, ref time, g);
  310.                 }
  311.             }
  312.             g.color[u] = black;
  313.             g.c[u] = time;
  314.             time++;
  315.         }
  316.  
  317.         public static void FordBellman(int u, Graph g)
  318.         {
  319.             int n = g.g.Length;
  320.             for (int i = 0; i <= n; i++)
  321.             {
  322.                 g.d[i] = int.MaxValue;
  323.                 g.p[i] = 0;
  324.             }
  325.  
  326.             g.d[u] = 0;
  327.  
  328.             for (int i = 0; i < n - 1; i++)
  329.             {
  330.                 for (int j = 0; j < g.e.Count; j++)
  331.                 {
  332.                     if (g.d[g.e[j].a] != int.MaxValue)
  333.                     {
  334.                         if (g.d[g.e[j].a] + g.e[j].w < g.d[g.e[j].b])
  335.                         {
  336.                             g.d[g.e[j].b] = g.d[g.e[j].a] + g.e[j].w;
  337.                             g.p[g.e[j].b] = g.e[j].a;
  338.                         }
  339.                     }
  340.                 }
  341.             }
  342.         }
  343.     }*//*
  344.     static class ArrayUtils
  345.     {
  346.         public static int BinarySearch(int[] a, int val)
  347.         {
  348.             int left = 0;
  349.             int right = a.Length - 1;
  350.             int mid;
  351.  
  352.             while (left < right)
  353.             {
  354.                 mid = left + ((right - left) >> 1);
  355.                 if (val <= a[mid])
  356.                 {
  357.                     right = mid;
  358.                 }
  359.                 else
  360.                 {
  361.                     left = mid + 1;
  362.                 }
  363.             }
  364.  
  365.             if (a[left] == val)
  366.                 return left;
  367.             else
  368.                 return -1;
  369.         }
  370.  
  371.         public static double Bisection(F f, double left, double right, double eps)
  372.         {
  373.             double mid;
  374.             while (right - left > eps)
  375.             {
  376.                 mid = left + ((right - left) / 2d);
  377.                 if (Math.Sign(f(mid)) != Math.Sign(f(left)))
  378.                     right = mid;
  379.                 else
  380.                     left = mid;
  381.             }
  382.             return (left + right) / 2d;
  383.         }
  384.  
  385.  
  386.         public static decimal TernarySearchDec(Fdec f, decimal eps, decimal l, decimal r, bool isMax)
  387.         {
  388.             decimal m1, m2;
  389.             while (r - l > eps)
  390.             {
  391.                 m1 = l + (r - l) / 3m;
  392.                 m2 = r - (r - l) / 3m;
  393.                 if (f(m1) < f(m2))
  394.                     if (isMax)
  395.                         l = m1;
  396.                     else
  397.                         r = m2;
  398.                 else
  399.                     if (isMax)
  400.                         r = m2;
  401.                     else
  402.                         l = m1;
  403.             }
  404.             return r;
  405.         }
  406.  
  407.         public static double TernarySearch(F f, double eps, double l, double r, bool isMax)
  408.         {
  409.             double m1, m2;
  410.             while (r - l > eps)
  411.             {
  412.                 m1 = l + (r - l) / 3d;
  413.                 m2 = r - (r - l) / 3d;
  414.                 if (f(m1) < f(m2))
  415.                     if (isMax)
  416.                         l = m1;
  417.                     else
  418.                         r = m2;
  419.                 else
  420.                     if (isMax)
  421.                         r = m2;
  422.                     else
  423.                         l = m1;
  424.             }
  425.             return r;
  426.         }
  427.  
  428.         public static void Merge<T>(T[] A, int p, int q, int r, T[] L, T[] R) where T : IComparable<T>
  429.         {
  430.             for (int i = p; i <= q; i++)
  431.                 L[i] = A[i];
  432.             for (int i = q + 1; i <= r; i++)
  433.                 R[i] = A[i];
  434.  
  435.             for (int k = p, i = p, j = q + 1; k <= r; k++)
  436.             {
  437.                 if (i > q)
  438.                 {
  439.                     for (; k <= r; k++, j++)
  440.                         A[k] = R[j];
  441.                     return;
  442.                 }
  443.                 if (j > r)
  444.                 {
  445.                     for (; k <= r; k++, i++)
  446.                         A[k] = L[i];
  447.                     return;
  448.                 }
  449.                 if (L[i].CompareTo(R[j]) <= 0)
  450.                 {
  451.                     A[k] = L[i];
  452.                     i++;
  453.                 }
  454.                 else
  455.                 {
  456.                     A[k] = R[j];
  457.                     j++;
  458.                 }
  459.             }
  460.         }
  461.  
  462.         public static void Merge_Sort<T>(T[] A, int p, int r, T[] L, T[] R) where T : IComparable<T>
  463.         {
  464.             if (p >= r) return;
  465.             int q = p + ((r - p) >> 1);
  466.             Merge_Sort(A, p, q, L, R);
  467.             Merge_Sort(A, q + 1, r, L, R);
  468.             Merge(A, p, q, r, L, R);
  469.         }
  470.  
  471.         static void Shake<T>(T[] a)
  472.         {
  473.             Random rnd = new Random(Environment.TickCount);
  474.             T temp;
  475.             int b, c;
  476.             for (int i = 0; i < a.Length; i++)
  477.             {
  478.                 b = rnd.Next(0, a.Length);
  479.                 c = rnd.Next(0, a.Length);
  480.                 temp = a[b];
  481.                 a[b] = a[c];
  482.                 a[c] = temp;
  483.             }
  484.         }
  485.     }
  486.     */
  487. }
Advertisement
Add Comment
Please, Sign In to add comment