• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

洛谷P1337 [JSOI2004]平衡点 / 吊打XXX java实现

开发技术 开发技术 7天前 5次浏览

仍旧是一道模拟退火。

AC代码:(如果提交不成功,就多试几次吧~)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Random;
import java.util.StringTokenizer;

public class Main  implements Runnable{
    static int n,mcnt;
    static double t,t0,delta,resultX,resultY,energy,totalX,totalY;
    static int[][] info;
    static Random random = new Random(System.currentTimeMillis());
    public static void rrr() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        info = new int[n][3];
        int infox,infoy,weight;
        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            infox = Integer.parseInt(st.nextToken());
            infoy = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());
            info[i] = new int[]{infox,infoy,weight};
            totalX+=infox;
            totalY+=infoy;
        }
        t0 = 1e-15;
        delta = 0.996;
        mcnt = 5;
        energy = 1e10;

        mock();
        System.out.printf("%.3f %.3fn",resultX,resultY);
    }

    private static void mock(){
        for(int i = 0 ;i<mcnt;i++){
            SA();
        }
    }

    private static void SA(){
        double xx = resultX;
        double yy = resultY;
        t = 4000;
        while (t>t0){
            double xtemp = xx+(Math.random()*2-(double)random.nextInt())*t;
            double ytemp = yy+(Math.random()*2-(double)random.nextInt())*t;
            double currentEnergy = getAllEnergy(xtemp,ytemp);
            double D = currentEnergy-energy;
            if(D<0){
                energy = currentEnergy;
                resultX = xtemp;
                resultY = ytemp;
                xx = xtemp;
                yy = ytemp;
            }
            else if(Math.pow(Math.E,-D/t)>Math.random()){
                xx = xtemp;
                yy = ytemp;
            }
            t*=delta;
        }
    }

    private static double getAllEnergy(double x,double y){
        double allEnergy = 0;
        for(int i = 0;i<n;i++){
            allEnergy+=Math.sqrt(Math.pow(x-info[i][0],2)+Math.pow(y-info[i][1],2))*info[i][2];
        }
        return allEnergy;
    }

    @Override
    public void run() {
        try {
            rrr();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        new Thread(null,new Main(),"",1<<29).start();
    }
}

程序员灯塔
转载请注明原文链接:洛谷P1337 [JSOI2004]平衡点 / 吊打XXX java实现
喜欢 (0)