hihocoder45

http://hihocoder.com/contest/offers45/problems
题目1 : 互补二元组
移项化为x_i-y_i=y_j-x_j

package l451;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        Map<Integer, Integer>map=new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++) {
            int d=sc.nextInt()-sc.nextInt();
            map.put(d, map.containsKey(d)?1+map.get(d):1);
        }
        
        long res=0;
        for(int i:map.keySet())
            if(i>0 && map.containsKey(-i)) res+=map.get(i)*map.get(-i);
        if(map.containsKey(0)) {
            int t=map.get(0);
            res+=((long)t*(t-1)/2);
        }
        System.out.println(res);
    }
}

题目2 : 寻找切线
先找到4个边界上的点，然求出所有其他点与当前点的斜率

package l452;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]xs=new int[n],ys=new int[n];
        int minx=Integer.MAX_VALUE, minIdx=-1;
        for(int i=0;i<n;i++) {
            xs[i]=sc.nextInt();
            ys[i]=sc.nextInt();
            if(xs[i]<minx) {
                minx=xs[i];
                minIdx=i;
            }
        }
        
        double maxSlope=Integer.MIN_VALUE;
        int maxIdx=-1;
        for(int i=0;i<n;i++) {
            if(i==minIdx) continue;
            if(xs[i]==minx) {maxIdx=i;break;}
            double d=(ys[i]-ys[minIdx]+0.0)/(xs[i]-xs[minIdx]);
            if(d>maxSlope){
                maxSlope=d;
                maxIdx=i;
            }
        }
        System.out.println((1+minIdx)+" "+(1+maxIdx));
    }
}

题目3 : LR问题
模拟自己玩一遍就好了

package l453;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s=sc.next(), t=sc.next();
        if(s.length()!=t.length()) {
            System.out.println(-1);
            return;
        }
        char[]cs=s.toCharArray(),ct=t.toCharArray();
        int res=0;
        
        int i=0,j=0,n=s.length();
        while(i<s.length()) {
            int r1=0,l1=0,r2=0,l2=0;
            j=i;
            while(j<n){
                if((cs[j]=='R'||ct[j]=='R') && (l1+l2>0)) break;
                if((cs[j]=='L'||ct[j]=='L') && (r1+r2>0)) break;
                if(cs[j]=='R')          r1++;
                else if(cs[j]=='L')     l1++;
                if(ct[j]=='R')          r2++;
                else if(ct[j]=='L')     l2++;
                j++;
            }
            char tt=(l1+l2>0)?'L':'R';
            List<Integer> a1=new ArrayList<Integer>(), a2=new ArrayList<Integer>();
            for(int k=i;k<j;k++) {
                if(cs[k]!='_') a1.add(k);
                if(ct[k]!='_') a2.add(k);
            }
            int sum=0;
            for(int k=0;k<a1.size();k++) {
                if((tt=='L' && a1.get(k)<a2.get(k)) || (tt=='R' && a1.get(k)>a2.get(k))) {
                    System.out.println(-1);
                    return;
                }
                sum += Math.abs(a1.get(k)-a2.get(k));
            }
            res+=sum;
            
            i=j;
        }
        
        
        System.out.println(res);
    }
}

题目4 : 推断大小关系
二分+BFS（去重）
不想写啦。。。。