import java.util.*;
import java.util.function.Consumer;

class Constants {
    public static final float PI = 3.1415926535f;
    public static final float DEFAULT_ENTITY_RADIUS = 0.5f;
    public static final float HEAD_OFFSET_Y = -1.0f;
    public static final float DEFAULT_TRACE_SPEED = 15.0f;
    public static final float MAX_TRACE_DISTANCE = 100.0f;
    public static final float DEFAULT_TRACE_LIFETIME = 3.0f;
    public static final float CRIT_CHANCE = 0.15f;
    public static final float CRIT_MULTIPLIER = 1.8f;
    public static final float HEADSHOT_MULTIPLIER = 2.2f;
    public static final float DAMAGE_DECAY_RATE = 0.005f;
    public static final float EPSILON = 1e-6f;
}

enum DamageType {
    PHYSICAL, MAGICAL, TRUE
}

enum BulletFeature {
    NORMAL, PENETRATE, EXPLOSIVE, ARMOR_PIERCE
}

class Vector2 {
    float x, y;

    public Vector2() {
        this(0.0f, 0.0f);
    }

    public Vector2(float x, float y) {
        this.x = x;
        this.y = y;
    }

    public Vector2 add(Vector2 other) {
        return new Vector2(x + other.x, y + other.y);
    }

    public Vector2 subtract(Vector2 other) {
        return new Vector2(x - other.x, y - other.y);
    }

    public Vector2 multiply(float scalar) {
        return new Vector2(x * scalar, y * scalar);
    }

    public Vector2 divide(float scalar) {
        return Math.abs(scalar) < Constants.EPSILON ? new Vector2() : new Vector2(x / scalar, y / scalar);
    }

    public float length() {
        return (float) Math.sqrt(x * x + y * y);
    }

    public float lengthSquared() {
        return x * x + y * y;
    }

    public Vector2 normalize() {
        float len = length();
        return len < Constants.EPSILON ? new Vector2(1, 0) : divide(len);
    }

    public float distance(Vector2 other) {
        return subtract(other).length();
    }

    public float distanceSquared(Vector2 other) {
        return subtract(other).lengthSquared();
    }

    public static Vector2 predictTargetPos(Vector2 targetPos, Vector2 targetVel, float bulletSpeed, float dist) {
        float timeToHit = dist / bulletSpeed;
        return targetPos.add(targetVel.multiply(timeToHit));
    }
}

class DetectionRegionConfig {
    float angleSize = 360.0f;
    float radius = 99.9f;
    float height = 99.9f;
    float effectiveDistance = 9999.0f;
    float duration = 9999.0f;
    float judgmentDelay = 0.0001f;
    boolean adaptation = true;
    float upperLimitThresholdSize = 99.9f;
    float movementCompensation = 99.9f;
    float jumpCompensation = 99.9f;
    float vestCompensation = 99.9f;
    float stationaryCompensation = 99.9f;
    float globalScale = 99.9f;
    float extraRadiusMultiplier = 99.9f;
    boolean noBackfaceCulling = true;
    boolean forceSphereCast = true;
    boolean ignoreOcclusion = true;
    boolean affectOnlyTarget = false;
}

class DetectionRegionManager {
    private static DetectionRegionManager instance;
    private Map<String, DetectionRegionConfig> configs = new HashMap<>();

    private DetectionRegionManager() {
        initDefaults();
    }

    public static DetectionRegionManager getInstance() {
        if (instance == null) {
            instance = new DetectionRegionManager();
        }
        return instance;
    }

    public void loadConfig(String name, DetectionRegionConfig cfg) {
        if (!name.isEmpty()) {
            configs.put(name, cfg);
        }
    }

    public DetectionRegionConfig getConfig(String name) {
        DetectionRegionConfig cfg = configs.get(name);
        return cfg != null ? cfg : new DetectionRegionConfig();
    }

    private void initDefaults() {
        loadConfig("DRV_Head", new DetectionRegionConfig());
        loadConfig("DRV_Body", new DetectionRegionConfig());
        loadConfig("DRV_Limb", new DetectionRegionConfig());
        loadConfig("DRV_Global", maximizeConfig());
    }

    private DetectionRegionConfig maximizeConfig() {
        DetectionRegionConfig cfg = new DetectionRegionConfig();
        cfg.radius = 1e9f;
        cfg.height = 1e9f;
        cfg.effectiveDistance = 1e9f;
        cfg.duration = 1e9f;
        cfg.angleSize = 360.0f;
        cfg.ignoreOcclusion = true;
        cfg.affectOnlyTarget = false;
        return cfg;
    }
}

class Entity {
    private Vector2 pos;
    private Vector2 velocity;
    private float hp;
    private float maxHp;
    private float defense;
    private float magicResist;
    private float radius;
    private DamageType weakType;
    private boolean isMoving;

    public Entity(float hp, float defense, float magicResist, DamageType weakType) {
        this.maxHp = hp;
        this.hp = hp;
        this.defense = defense;
        this.magicResist = magicResist;
        this.weakType = weakType;
        this.radius = Constants.DEFAULT_ENTITY_RADIUS;
        this.velocity = new Vector2();
        this.isMoving = false;
    }

    public Vector2 getPos() {
        return pos;
    }

    public void setPos(Vector2 newPos) {
        velocity = newPos.subtract(pos);
        isMoving = velocity.lengthSquared() > Constants.EPSILON;
        pos = newPos;
    }

    public Vector2 getVelocity() {
        return velocity;
    }

    public float getHp() {
        return hp;
    }

    public float getMaxHp() {
        return maxHp;
    }

    public float getRadius() {
        return radius;
    }

    public float getDefense() {
        return defense;
    }

    public float getMagicResist() {
        return magicResist;
    }

    public DamageType getWeakType() {
        return weakType;
    }

    public boolean isMoving() {
        return isMoving;
    }

    public Vector2 getHeadPos() {
        return new Vector2(pos.x, pos.y + Constants.HEAD_OFFSET_Y);
    }

    public void takeDamage(float rawDamage, DamageType type, boolean isHeadShot, boolean isCrit) {
        float finalDamage = rawDamage;
        if (isCrit) finalDamage *= Constants.CRIT_MULTIPLIER;
        if (isHeadShot) finalDamage *= Constants.HEADSHOT_MULTIPLIER;

        switch (type) {
            case PHYSICAL:
                finalDamage = Math.max(0.0f, finalDamage - defense * 0.8f);
                break;
            case MAGICAL:
                finalDamage = Math.max(0.0f, finalDamage - magicResist * 0.9f);
                break;
            case TRUE:
                break;
        }

        if (type == weakType) finalDamage *= 1.3f;

        hp = Math.max(0.0f, hp - finalDamage);
        onHit(finalDamage, type, isHeadShot, isCrit);
    }

    protected void onHit(float damage, DamageType type, boolean isHeadShot, boolean isCrit) {}

    public boolean isAlive() {
        return hp > 0.0f;
    }
}

class HitCircle {
    protected Vector2 center;
    protected float radius;
    protected float damage;
    protected DamageType damageType;
    protected DetectionRegionConfig cfg;
    protected boolean isActive;
    protected Consumer<HitCircleData> onHit;

    public interface HitCircleData {
        HitCircle getBullet();
        Entity getVictim();
        float getDamage();
        boolean isHeadShot();
        boolean isCrit();
    }

    public HitCircle(Vector2 center, float radius, float damage, DamageType damageType) {
        this.center = center;
        this.radius = radius;
        this.damage = damage;
        this.damageType = damageType;
        this.isActive = true;
    }

    public boolean isPointInRange(Vector2 point) {
        if (!isActive) return false;
        return center.distanceSquared(point) <= radius * radius;
    }

    public boolean isEntityInRange(Entity entity) {
        if (!isActive || !entity.isAlive()) return false;
        float totalRadius = radius + entity.getRadius();
        return center.distanceSquared(entity.getPos()) <= totalRadius * totalRadius;
    }

    public void applyDamage(Entity victim, boolean isCrit) {
        if (!isActive || !isEntityInRange(victim)) return;

        Vector2 headPos = victim.getHeadPos();
        boolean isHeadShot = center.distanceSquared(headPos) <= (radius + 0.2f) * (radius + 0.2f);
        if (onHit != null) {
            onHit.accept(() -> new HitCircleData() {
                @Override
                public HitCircle getBullet() { return HitCircle.this; }
                @Override
                public Entity getVictim() { return victim; }
                @Override
                public float getDamage() { return damage; }
                @Override
                public boolean isHeadShot() { return isHeadShot; }
                @Override
                public boolean isCrit() { return isCrit; }
            });
        } else {
            victim.takeDamage(damage, damageType, isHeadShot, isCrit);
        }
    }

    public boolean update(float deltaTime) {
        return isActive;
    }

    public void setActive(boolean active) {
        isActive = active;
    }

    public boolean isActive() {
        return isActive;
    }

    public Vector2 getCenter() {
        return center;
    }

    public void setCenter(Vector2 center) {
        this.center = center;
    }

    public float getRadius() {
        return radius;
    }

    public void setRadius(float radius) {
        this.radius = Math.max(0.0f, radius);
    }

    public float getDamage() {
        return damage;
    }

    public void setDamage(float damage) {
        this.damage = Math.max(0.0f, damage);
    }

    public DamageType getDamageType() {
        return damageType;
    }

    public void setOnHit(Consumer<HitCircleData> onHit) {
        this.onHit = onHit;
    }
}

class HomingBullet extends HitCircle {
    private Entity target;
    private float speed;
    private float maxTraceDist;
    private float lifeTime;
    private float elapsedTime;
    private float headDetectionRad;
    private BulletFeature feature;
    private int penetrateCount;
    private final int maxPenetrate = 2;
    private float spawnDist;
    private Random random = new Random();

    public HomingBullet(Vector2 spawnPos, Entity target, float damage, DamageType type, BulletFeature feature) {
        super(spawnPos, 0.2f, damage, type);
        this.target = target;
        this.speed = Constants.DEFAULT_TRACE_SPEED;
        this.maxTraceDist = Constants.MAX_TRACE_DISTANCE;
        this.lifeTime = Constants.DEFAULT_TRACE_LIFETIME;
        this.elapsedTime = 0.0f;
        this.headDetectionRad = 0.3f;
        this.feature = feature;
        this.penetrateCount = 0;
        this.spawnDist = target != null ? spawnPos.distance(target.getPos()) : 0;

        if (feature == BulletFeature.PENETRATE) setRadius(0.3f);
        if (feature == BulletFeature.EXPLOSIVE) setRadius(0.5f);

        setOnHit(data -> {
            float finalDmg = data.getDamage();
            if (feature == BulletFeature.ARMOR_PIERCE) finalDmg *= 1.3f;
            if (feature == BulletFeature.EXPLOSIVE) {
                explodeDamage(data.getVictim(), finalDmg, data.isCrit());
                data.getBullet().setActive(false);
                return;
            }
            data.getVictim().takeDamage(finalDmg, data.getBullet().getDamageType(), data.isHeadShot(), data.isCrit());
            if (feature != BulletFeature.PENETRATE || penetrateCount >= maxPenetrate) {
                data.getBullet().setActive(false);
            } else penetrateCount++;
        });
    }

    private void explodeDamage(Entity mainTarget, float dmg, boolean isCrit) {
        float explodeRad = 1.5f;
        List<Entity> entities = getNearbyEntities(mainTarget.getPos(), explodeRad);
        for (Entity ent : entities) {
            float distRatio = mainTarget.getPos().distance(ent.getPos()) / explodeRad;
            float explodeDmg = dmg * (1 - distRatio * 0.5f);
            ent.takeDamage(explodeDmg, getDamageType(), false, isCrit);
        }
    }

    private List<Entity> getNearbyEntities(Vector2 pos, float rad) {
        return new ArrayList<>();
    }

    @Override
    public boolean update(float deltaTime) {
        if (!isActive || target == null || !target.isAlive()) return false;

        elapsedTime += deltaTime;
        lifeTime -= deltaTime;
        if (lifeTime <= 0.0f) {
            setActive(false);
            return false;
        }

        Vector2 currPos = getCenter();
        Vector2 targetHead = target.getHeadPos();
        float currDist = currPos.distance(targetHead);

        if (currDist > maxTraceDist) {
            setActive(false);
            return false;
        }

        float distFromSpawn = currPos.distance(super.getCenter());
        float decayRatio = 1 - distFromSpawn * Constants.DAMAGE_DECAY_RATE;
        setDamage(super.getDamage() * Math.max(0.5f, decayRatio));

        Vector2 targetPos = target.isMoving()
                ? Vector2.predictTargetPos(targetHead, target.getVelocity(), speed, currDist)
                : targetHead;

        Vector2 dir = targetPos.subtract(currPos).normalize();
        Vector2 moveStep = dir.multiply(speed * deltaTime);
        setCenter(currPos.add(moveStep));

        if (currDist < speed * deltaTime + 0.1f) {
            applyDamage(target, isCrit());
            return false;
        }

        return true;
    }

    public boolean isCrit() {
        return random.nextFloat() < Constants.CRIT_CHANCE;
    }

    public BulletFeature getFeature() {
        return feature;
    }
}

class SpatialGrid {
    private float cellSize;
    private Map<Integer, List<Integer>> grid = new HashMap<>();

    public SpatialGrid(float cellSize) {
        this.cellSize = cellSize;
    }

    public void clear() {
        grid.clear();
    }

    public void insert(int bulletIdx, HitCircle bullet) {
        if (!bullet.isActive()) return;
        int cellID = getCellID(bullet.getCenter());
        grid.computeIfAbsent(cellID, k -> new ArrayList<>()).add(bulletIdx);
    }

    public List<Integer> getCandidateBullets(Vector2 pos) {
        int cellID = getCellID(pos);
        return grid.getOrDefault(cellID, new ArrayList<>());
    }

    private int getCellID(Vector2 pos) {
        int x = (int) Math.floor(pos.x / cellSize);
        int y = (int) Math.floor(pos.y / cellSize);
        return x * 10000 + y;
    }
}

class HitCircleManager {
    private List<HomingBullet> bullets = new ArrayList<>();
    private SpatialGrid spatialGrid;

    public HitCircleManager() {
        this.spatialGrid = new SpatialGrid(15.0f);
    }

    public int addHomingBullet(Vector2 spawnPos, Entity target, float damage, DamageType type, BulletFeature feature) {
        if (target == null || !target.isAlive()) return -1;
        bullets.add(new HomingBullet(spawnPos, target, damage, type, feature));
        return bullets.size() - 1;
    }

    public void updateBullets(float deltaTime) {
        Iterator<HomingBullet> iterator = bullets.iterator();
        while (iterator.hasNext()) {
            HomingBullet bullet = iterator.next();
            if (!bullet.update(deltaTime)) iterator.remove();
        }
    }

    public void checkAndApplyDamage(List<Entity> world) {
        spatialGrid.clear();
        for (int i = 0; i < bullets.size(); i++) {
            HomingBullet bullet = bullets.get(i);
            if (bullet.isActive()) spatialGrid.insert(i, bullet);
        }

        for (Entity entity : world) {
            if (!entity.isAlive()) continue;
            List<Integer> candidateIdx = spatialGrid.getCandidateBullets(entity.getPos());
            for (int idx : candidateIdx) {
                if (idx < bullets.size()) {
                    HomingBullet bullet = bullets.get(idx);
                    if (bullet.isActive()) bullet.applyDamage(entity, bullet.isCrit());
                }
            }
        }
    }

    public void displayBullets() {
        System.out.println("\n" + bullets.size());
        for (int i = 0; i < bullets.size(); i++) {
            HomingBullet b = bullets.get(i);
            System.out.printf("%d %.2f %.2f %.2f%n", i, b.getCenter().x, b.getCenter().y, b.getDamage());
        }
    }

    public int getActiveBulletCount() {
        return bullets.size();
    }

    public void clearAllBullets() {
        bullets.clear();
    }
}

public class Main {
    public static void main(String[] args) {
        HitCircleManager bulletMgr = new HitCircleManager();
        List<Entity> entities = new ArrayList<>();

        entities.add(new Entity(150.0f, 20.0f, 5.0f, DamageType.PHYSICAL));
        entities.add(new Entity(80.0f, 5.0f, 25.0f, DamageType.MAGICAL));
        entities.add(new Entity(100.0f, 10.0f, 10.0f, DamageType.TRUE));
        entities.add(new Entity(120.0f, 15.0f, 8.0f, DamageType.PHYSICAL));

        entities.get(0).setPos(new Vector2(10, 0));
        entities.get(1).setPos(new Vector2(25, 5));
        entities.get(2).setPos(new Vector2(40, 2));
        entities.get(3).setPos(new Vector2(55, -3));

        bulletMgr.addHomingBullet(new Vector2(0, 3), entities.get(0), 35.0f, DamageType.PHYSICAL, BulletFeature.ARMOR_PIERCE);
        bulletMgr.addHomingBullet(new Vector2(0, 3), entities.get(1), 30.0f, DamageType.MAGICAL, BulletFeature.EXPLOSIVE);
        bulletMgr.addHomingBullet(new Vector2(0, 3), entities.get(2), 25.0f, DamageType.TRUE, BulletFeature.PENETRATE);
        bulletMgr.addHomingBullet(new Vector2(0, 3), entities.get(3), 28.0f, DamageType.PHYSICAL, BulletFeature.NORMAL);

        final float deltaTime = 0.03f;
        int frame = 0;
        while (bulletMgr.getActiveBulletCount() > 0 && frame < 200) {
            if (frame % 10 == 0) {
                for (int i = 0; i < entities.size(); i++) {
                    Vector2 currPos = entities.get(i).getPos();
                    float yStep = i % 2 == 0 ? 0.2f : -0.2f;
                    entities.get(i).setPos(new Vector2(currPos.x + 0.5f, currPos.y + yStep));
                }
            }
            bulletMgr.updateBullets(deltaTime);
            bulletMgr.checkAndApplyDamage(entities);
            bulletMgr.displayBullets();
            for (int i = 0; i < entities.size(); i++) {
                Entity ent = entities.get(i);
                System.out.printf("%d %.1f/%.1f%n", i, ent.getHp(), ent.getMaxHp());
            }
            frame++;
        }

        for (int i = 0; i < entities.size(); i++) {
            Entity ent = entities.get(i);
            System.out.printf("%d %d %.1f%n", i, ent.isAlive() ? 1 : 0, ent.getHp());
        }
    }
}