EvbCFfp1XB

problem and my answer.



Approach

684468.79 RandomForest
689847.94 RandomForest + medianfilter +-1
693728.97 RandomForest + medianfilter +-5

RandomForest は 1 image あたり 15625 samples,
feature は +-delta(=4, 8) の正方形の色の{平均、歪度,尖度} * 正方形の中心{ (r,c), (r-delta,c-delta), (r-delta,c+delta), (r+delta,c-delta), (r+delta,c+delta)} * 4色{gray, red, green, blue}。


chainerは、 VOC2012 で練習中で間に合わなかった。



ダメだったアプローチ


 * 事前計算されたDP
  
各試験紙に同じ数のボトルを割り当てると仮定して、
   DP[毒の数][試験紙の数][残りラウンド数] = 期待値が最大になるようなボトルの割合。
   TLE。

 * 各試験紙に同じ数のボトルを割り当てると仮定して、SA, 深さ制限dfs with 黄金分割探索。


使ったアプローチ


 * 試験紙が毒の数より圧倒的に多いとき、
   二分探索のようにして、毒の範囲をしぼる。

 * 試験紙>=毒の数のとき、
   試験紙の補集合も一枚の試験紙のように使える。
   残りのラウンドを見て、試験紙にボトルを等分する。

 * その他
   毎ラウンド、シミュレーションして (再利用できる試験紙の数 ^ 残りラウンド数) * ボトルの数 が最大になるように、試験紙にボトルを割り当てる。




source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Objects;
import java.util.TimeZone;

public class PoisonedWine {
private static final int unknown = 0;
private static final int good = -1;
private static final int bad = -2;

public static final Watch watch = new Watch();
public static final XorShift rng = new XorShift(System.nanoTime());

private int numBottles;
private int numRounds;
private int numPoisonedBottles;
private int numPapers;

private int numGoods;
private int numBads;
private int availablePapers;
private int[] states;

public int[] testWine(int numBottles, int numPapers, int numRounds, int numPoisonedBottles) {
CalendarUtils.printDate(Constants.currentTime, Constants.endTime);

if (numPoisonedBottles > numPapers + 5) {
return new PoisonedWineSubmission3().testWine(numBottles, numPapers, numRounds, numPoisonedBottles);
}

init(numBottles, numPapers, numRounds, numPoisonedBottles);

solve();

int[] makeSolution = makeSolution(states);

Utils.debug("time", watch.getSecondString(), "score", calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods);
return makeSolution;
}

private int nextRestartRound = 0;

private void solve() {
Bottles unknownBottles = restart(numBottles, numPoisonedBottles, states);

Utils.debug("round", "numBottles", "score", "numGoods", "Papers", "size", "prob", "ev");

for (int round = 0; round < numRounds; round++) {

if (availablePapers == 0) {
break;
}
ArrayList<Group> groups = makeGroup(unknownBottles, round);

test(groups);

update(groups);

{
ArrayList<Integer> sizes = new ArrayList<>();
for (Group group : groups) {
sizes.add(group.bottles.get(0).indexes2.size());
}

if (!sizes.isEmpty()) {
Utils.debug(round, unknownBottles.indexes2.size(), (int) calculateScore(numBottles, numPoisonedBottles, numGoods), numGoods, availablePapers, sizes);
} else {
Utils.debug(round, unknownBottles.indexes2.size(), (int) calculateScore(numBottles, numPoisonedBottles, numGoods), numGoods, availablePapers);
}
}

if (groups.size() == 1) {
unknownBottles.indexes2 = groups.get(0).complement.indexes2;
unknownBottles.infBads = groups.get(0).complement.supBads;
unknownBottles.supBads = groups.get(0).complement.supBads;

if (unknownBottles.isAllGood()) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
} else if (round + 1 == nextRestartRound) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
} else {
}
} else {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
}
}

}

private void update(ArrayList<Group> groups) {
for (Group group : groups) {
for (Bottles bottles : group.bottles) {
if (bottles.isAllGood()) {
updateStateGood(bottles.indexes2);
}
if (bottles.isAllBad()) {
updateStateBad(bottles.indexes2);
}
updateExpectedProbability(bottles.indexes2, (double) bottles.infBads / bottles.indexes2.size());
}
{
if (group.complement.isAllGood()) {
updateStateGood(group.complement.indexes2);
}
if (group.complement.isAllBad()) {
updateStateBad(group.complement.indexes2);
}
updateExpectedProbability(group.complement.indexes2, (double) group.complement.supBads / group.complement.indexes2.size());
}
}
}

private Bottles restart(int numBottles, int numPoisonedBottles, int[] states) {
Bottles bottles = new Bottles();

for (int i = 0; i < numBottles; i++) {
if (states[i] == bad) {
} else if (states[i] == good) {
} else {
bottles.indexes2.add(i);
}
}

bottles.infBads = numPoisonedBottles;
bottles.supBads = numPoisonedBottles;

updateExpectedProbability(bottles.indexes2, (double) bottles.supBads / bottles.indexes2.size());

ArrayList<Pair<Double, Integer>> countAndIndexPairs = new ArrayList<>();
for (int i = 0; i < bottles.indexes2.size(); i++) {
int index = bottles.indexes2.get(i).intValue();
countAndIndexPairs.add(new Pair<Double, Integer>(maxExpectedProbability[index] + 1e-6 * rng.nextDouble(), index));
}
Collections.sort(countAndIndexPairs);

bottles.indexes2.clear();
for (int i = 0; i < countAndIndexPairs.size(); i++) {
bottles.indexes2.add(countAndIndexPairs.get(i).second.intValue());
}

numBottlesAtRestart = bottles.indexes2.size();

double paperPerPoison = (double) numPapers / numPoisonedBottles;
int restartRounds = (int) Math.ceil(numRounds / paperPerPoison);
nextRestartRound += restartRounds;

Utils.debug("restart", "unknowns.size()", bottles.indexes2.size(), "numPoisonedBottles - numBads", numPoisonedBottles + " - " + numBads + " = " + (numPoisonedBottles - numBads));

return bottles;
}

private int numBottlesAtRestart;
private double[] maxExpectedProbability;
private double[] minExpectedProbability;

private void updateExpectedProbability(ArrayList<Integer> indexes, double p) {
for (Integer index : indexes) {
maxExpectedProbability[index.intValue()] = Math.max(maxExpectedProbability[index.intValue()], p);
minExpectedProbability[index.intValue()] = Math.min(maxExpectedProbability[index.intValue()], p);
}
}

private void updateStateBad(ArrayList<Integer> indexes) {
for (Integer index : indexes) {
if (states[index.intValue()] == unknown) {
states[index.intValue()] = bad;
numBads++;
}
}
}

private void updateStateGood(ArrayList<Integer> indexes2) {
for (Integer index : indexes2) {
if (states[index.intValue()] == unknown) {
states[index.intValue()] = good;
numGoods++;
}
}
}

private void test(ArrayList<Group> groups) {
ArrayList<Bottles> bottles = new ArrayList<>();
ArrayList<Group> groups2 = new ArrayList<>();
for (Group group : groups) {
for (int j = 0; j < group.bottles.size(); j++) {
if (group.bottles.get(j).indexes2.size() == 0) {
continue;
}

bottles.add(group.bottles.get(j));
groups2.add(group);
}
}

boolean[] isPoisoned = useTestStrips(bottles);
assert isPoisoned.length == bottles.size();

for (int i = 0; i < isPoisoned.length; i++) {
if (isPoisoned[i]) {
bottles.get(i).supBads = groups2.get(i).supBads;
bottles.get(i).infBads = 1;

groups2.get(i).complement.supBads--;
groups2.get(i).complement.infBads = 0;
availablePapers--;
} else {
bottles.get(i).supBads = 0;
bottles.get(i).infBads = 0;
}
}

for (Group group : groups) {
int sumInfBads = 0;
for (Bottles bottles2 : group.bottles) {
sumInfBads += bottles2.infBads;
}
for (Bottles bottles2 : group.bottles) {
bottles2.supBads = Math.min(bottles2.supBads, group.supBads - (sumInfBads - bottles2.infBads));
}
}

}

private ArrayList<Group> makeGroup(Bottles bottles0, int round) {
if (bottles0.isAllGood() || bottles0.isAllBad()) {
return new ArrayList<>();
}

ArrayList<Group> groups2 = new ArrayList<>();

int numGroups = availablePapers / (2 * bottles0.supBads - 1);
numGroups /= numRounds - round;
if (numGroups == 0) {
numGroups = 1;
}

for (int i = 0; i < numGroups; i++) {
groups2.add(new Group(bottles0.infBads, bottles0.supBads));
}

int[] groupPapers = new int[numGroups];
for (int paper = 0; paper < availablePapers; paper++) {
groupPapers[paper % groups2.size()]++;
}

for (int i = 0; i < numGroups; i++) {
Group group = groups2.get(i);

Result bestResult = new Result();
double paperPerPoison = (double) numPapers / numPoisonedBottles;
int restartRounds = (int) Math.ceil(numRounds / paperPerPoison);
double eachRoundBottles = (double) numBottlesAtRestart / restartRounds;
int complement = (round + 1 == nextRestartRound) ? 1 : 0;
double size = eachRoundBottles / (groupPapers[i] + complement);

bestResult.bestSize = (int) Math.round(size);
if (bestResult.bestSize == 0) {
bestResult.bestSize = 1;
}

for (int paper = 0; paper < groupPapers[i]; paper++) {
group.bottles.add(new Bottles());
}

for (int sizeIndex = 0; sizeIndex < bottles0.indexes2.size(); sizeIndex++) {
int toIndex = sizeIndex;
for (int j = 0; j < i; j++) {
toIndex /= (group.bottles.size() + 1);
}
toIndex = toIndex % (group.bottles.size() + 1);
int value = bottles0.indexes2.get(sizeIndex).intValue();

if (toIndex >= 0 && toIndex < group.bottles.size() && group.bottles.get(toIndex).indexes2.size() < bestResult.bestSize) {
group.bottles.get(toIndex).indexes2.add(value);
} else {
group.complement.indexes2.add(value);
}
}

}
return groups2;
}

private void init(int numBottles, int numPapers, int numRounds, int numPoisonedBottles) {
Utils.debug("numBottles", numBottles, "numPapers", numPapers, "numRounds", numRounds, "numPoisonedBottles", numPoisonedBottles);

this.numBottles = numBottles;
this.numPapers = numPapers;
this.numRounds = numRounds;
this.numPoisonedBottles = numPoisonedBottles;

this.states = new int[numBottles];
Arrays.fill(states, unknown);
this.maxExpectedProbability = new double[numBottles];
Arrays.fill(maxExpectedProbability, 0);
this.minExpectedProbability = new double[numBottles];
Arrays.fill(minExpectedProbability, 1);

this.numGoods = 0;
this.numBads = 0;

this.availablePapers = numPapers;
}

private double calculateScore(int numBottles, int numPoisonedBottles, int numGoods) {
double d = (double) numGoods / (numBottles - numPoisonedBottles);
double score = 1e6 * d * d;
return score;
}

private int[] makeSolution(int[] states) {
ArrayList<Integer> unknownAndBad = new ArrayList<>();
for (int i = 0; i < states.length; i++) {
if (states[i] != good) {
unknownAndBad.add(i);
}
}
int[] ret = new int[unknownAndBad.size()];
for (int i = 0; i < unknownAndBad.size(); i++) {
ret[i] = unknownAndBad.get(i).intValue();
}
return ret;
}

private boolean[] useTestStrips(ArrayList<Bottles> bottles) {
String[] tests = new String[bottles.size()];
for (int i = 0; i < bottles.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < bottles.get(i).indexes2.size(); j++) {
if (j > 0) {
sb.append(",");
}
sb.append(bottles.get(i).indexes2.get(j));
}
tests[i] = sb.toString();
}

int[] testResults = PoisonTest.useTestStrips(tests);

boolean[] isPoisoned = new boolean[testResults.length];
for (int i = 0; i < isPoisoned.length; i++) {
isPoisoned[i] = testResults[i] == 1;
}
return isPoisoned;
}

public static void main(String[] args) {
try {
BR.br = new BufferedReader(new InputStreamReader(System.in));

int numBottles = BR.readInt();
int testPapers = BR.readInt();
int testRounds = BR.readInt();
int numPoison = BR.readInt();

PoisonedWine pw = new PoisonedWine();
int[] ret = pw.testWine(numBottles, testPapers, testRounds, numPoison);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Group {
ArrayList<Bottles> bottles;
Bottles complement;
int supBads;
int infBads;

public Group(int infBads, int supBads) {
bottles = new ArrayList<>();

this.supBads = supBads;
this.infBads = infBads;

complement = new Bottles();
complement.infBads = infBads;
complement.supBads = supBads;
}
}

class Bottles {
public boolean isComplement;
ArrayList<Integer> indexes2;
int supBads;
int infBads;

public Bottles() {
indexes2 = new ArrayList<>();
}

public boolean isAllGood() {
return supBads == 0;
}

public boolean isAllBad() {
return infBads >= indexes2.size();
}

@Override
public String toString() {
return Utils.toString("isComplement", isComplement, "supBads", supBads, "infBads", infBads, "size", indexes2.size());
}

}

class ArrayListInt {
private static final int DEFAULT_CAPACITY = 10;

private static final int[] EMPTY_ELEMENTDATA = {};

private static final int[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient int[] elementData;

private int size;

public ArrayListInt(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new int[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}

public ArrayListInt() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayListInt(ArrayListInt c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
elementData = Arrays.copyOf(elementData, size);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}

public void trimToSize() {
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}

public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public boolean contains(int o) {
return indexOf(o) >= 0;
}

public int indexOf(int o) {
for (int i = 0; i < size; i++)
if (o == elementData[i])
return i;
return -1;
}

public int lastIndexOf(int o) {
for (int i = size - 1; i >= 0; i--)
if (o == elementData[i])
return i;
return -1;
}

public Object clone() {
try {
ArrayListInt v = (ArrayListInt) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}

public int[] toArray() {
return Arrays.copyOf(elementData, size);
}

int elementData(int index) {
return elementData[index];
}

public int get(int index) {
rangeCheck(index);

return elementData(index);
}

public int set(int index, int element) {
rangeCheck(index);

int oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

public boolean add(int e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

public void add(int index, int element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}

public int removeByIndex(int index) {
rangeCheck(index);
int oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = 0;
return oldValue;
}

public boolean remove(int o) {
for (int index = 0; index < size; index++)
if (o == elementData[index]) {
fastRemove(index);
return true;
}
return false;
}

private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = 0;
}

public void clear() {
for (int i = 0; i < size; i++)
elementData[i] = 0;

size = 0;
}

public boolean addAll(ArrayListInt c) {
int[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

public boolean addAll(int index, ArrayListInt c) {
rangeCheckForAdd(index);

int[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

protected void removeRange(int fromIndex, int toIndex) {
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = 0;
}
size = newSize;
}

private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}

public boolean removeAll(ArrayListInt c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}

public boolean retainAll(ArrayListInt c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}

private boolean batchRemove(ArrayListInt c, boolean complement) {
final int[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
if (r != size) {
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = 0;
size = w;
modified = true;
}
}
return modified;
}
}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
System.err.flush();
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

final class Constants {
public static final boolean TIMER = true;
public static final boolean LOCAL = true;
public static final boolean DEBUG = true;
public static final boolean ASSERTION = true;

private static final String id = "GMT-4:00";
public static final Calendar currentTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
}

public static final Calendar startTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
startTime.set(2017, 7 - 1, 5, 21, 0, 0);
}

public static final Calendar endTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
endTime.set(2017, 7 - 1, 19, 21, 0, 0);
}

private Constants() {
}
}

class Result {
int bestSize;
double bestExpectedValue;
}

class CalendarUtils {
private CalendarUtils() {
}

public static final void printDate(Calendar currentTime, Calendar endTime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;

long end = endTime.getTimeInMillis();

long current = currentTime.getTimeInMillis();

long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);

int year = currentTime.get(Calendar.YEAR);
int month = 1 + currentTime.get(Calendar.MONTH);
int day = currentTime.get(Calendar.DAY_OF_MONTH);
int hour = currentTime.get(Calendar.HOUR_OF_DAY);
int minute = currentTime.get(Calendar.MINUTE);
int second = currentTime.get(Calendar.SECOND);

Utils.debug(String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes));
}

public static final String toStringDateAndTimeLeft(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes);
}

public static final String toStringDate(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("%02d/%02d/%02d %02d:%02d:%02d", year, month, day, hour, minute, second);
}

public static final String toStringTimeLeft(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("Time Left %d Hrs %d Mins", numHours, numMinutes);
}

}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class PoisonedWineSubmission3 {
private static final int unknown = 0;
private static final int good = -1;
private static final int bad = -2;

private XorShift rng = new XorShift(System.nanoTime());

public int[] testWine(int numBottles, int numStrips, int numRounds, int numPoisonedBottles) {
Utils.debug("numBottles", numBottles, "numStrips", numStrips, "numRounds", numRounds, "numPoisonedBottles", numPoisonedBottles);

int[] states = new int[numBottles];
Arrays.fill(states, unknown);

int numGoods = 0;
int numBads = 0;

int availableStrips = numStrips;
ArrayListInt all = new ArrayListInt();
for (int i = 0; i < numBottles; i++) {
all.add(i);
}
int[] array = all.toArray();
shuffle(array, rng);
BottlesSubmission3 unknownBottles = new BottlesSubmission3(array, numPoisonedBottles, false);
for (int round = 0; round < numRounds; round++) {

if (availableStrips == 0) {
break;
}

if (unknownBottles.indexes.length == 0) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
}

if (unknownBottles.isAllBad() || unknownBottles.isAllGood()) {
if (unknownBottles.isAllGood()) {
for (int index : unknownBottles.indexes) {
states[index] = good;
numGoods++;
}
}
unknownBottles = restart(numBottles, numPoisonedBottles, states);
if (unknownBottles.isAllBad() || unknownBottles.isAllGood()) {
break;
}
}
boolean[] simpleModel = getSimpleModel(unknownBottles.indexes.length, unknownBottles.numBads);

int maxBatchSize = (int) (Math.ceil((double) unknownBottles.indexes.length / (availableStrips)));

double bestBatchSize2 = -1;
double bestNumGoods = -1;

for (int batchSize = 1; batchSize <= maxBatchSize; batchSize++) {

int nextStrips = 0;
for (int strip = 0; strip < availableStrips; strip++) {
if (isGood(simpleModel, batchSize, strip)) {
nextStrips++;
}
}

if (Math.pow(nextStrips, numRounds - round) * batchSize > bestNumGoods) {
bestNumGoods = Math.pow(nextStrips, numRounds - round) * batchSize;
bestBatchSize2 = batchSize;
}

}
int bestBatchSize = (int) bestBatchSize2;
LinkedList<Integer> availableIndexes = new LinkedList<>();
for (int index : unknownBottles.indexes) {
availableIndexes.addLast(index);
}

ArrayList<BottlesSubmission3> bottleSets = new ArrayList<>();
for (int stripIndex = 0; stripIndex < availableStrips; stripIndex++) {
ArrayListInt indexes2 = new ArrayListInt();
for (int i = 0; i < bestBatchSize; i++) {
if (availableIndexes.size() > 0) {
indexes2.add(availableIndexes.pollFirst().intValue());
}
}

if (indexes2.size() > 0) {
bottleSets.add(new BottlesSubmission3(indexes2.toArray(), 0, true));
}
}

boolean[] isPoisoned = test((BottlesSubmission3[]) bottleSets.toArray(new BottlesSubmission3[bottleSets.size()]));
int nextBads = unknownBottles.numBads;

assert isPoisoned.length == bottleSets.size();

for (int i = 0; i < isPoisoned.length; i++) {
if (isPoisoned[i]) {
bottleSets.get(i).numBads = 1;
nextBads--;

if (bottleSets.get(i).indexes.length == 1) {
for (int index : bottleSets.get(i).indexes) {
states[index] = bad;
numBads++;
}
} else {
}
availableStrips--;
} else {
for (int index : bottleSets.get(i).indexes) {
states[index] = good;
numGoods++;
}
}
}
int[] toArray = new int[availableIndexes.size()];
for (int i = 0; i < toArray.length; i++) {
toArray[i] = availableIndexes.pollFirst().intValue();
}
unknownBottles = new BottlesSubmission3(toArray, nextBads, false);

Utils.debug("round", round, "score", (int) calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods, "Strips", availableStrips, "size", bestBatchSize);
}
int[] makeSolution = makeSolution(states);
Utils.debug("time", PoisonedWine.watch.getSecondString(), "score", calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods);

return makeSolution;

}

public static final void shuffle(int[] a, XorShift rng) {
for (int i = a.length - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
{
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
}

private boolean[] getSimpleModel(int numBottles, int numPoisonedBottles) {
boolean[] simpleModel = new boolean[numBottles];
{
double badProbability = (double) numPoisonedBottles / numBottles;
double sumBadProbability = 1e-9;
for (int i = 0; i < simpleModel.length; i++) {
sumBadProbability += badProbability;
if (sumBadProbability >= 1) {
sumBadProbability -= 1;
simpleModel[i] = true;
}
}

int count = 0;
for (int i = 0; i < simpleModel.length; i++) {
if (simpleModel[i]) {
count++;
}
}
assert count == numPoisonedBottles : Utils.toString(count, numPoisonedBottles, numBottles);
}
return simpleModel;
}

private boolean isGood(boolean[] simpleModel, int batchSize, int strip) {
for (int i = 0; i < batchSize; i++) {
if (strip * batchSize + i < simpleModel.length && simpleModel[strip * batchSize + i]) {
return false;
}
}
return true;
}

private double calculateScore(int numBottles, int numPoisonedBottles, int numGoods) {
double d = (double) numGoods / (numBottles - numPoisonedBottles);
double score = 1e6 * d * d;
return score;
}

private BottlesSubmission3 restart(int numBottles, int numPoisonedBottles, int[] states) {
int numBads = 0;
ArrayListInt unknowns = new ArrayListInt();
for (int i = 0; i < numBottles; i++) {
if (states[i] == bad) {
numBads++;
} else if (states[i] == good) {
} else {
unknowns.add(i);
}
}
Utils.debug("restart", "unknowns.size()", unknowns.size(), "numPoisonedBottles - numBads", numPoisonedBottles + " - " + numBads + " = " + (numPoisonedBottles - numBads));
int[] array = unknowns.toArray();
shuffle(array, rng);
return new BottlesSubmission3(array, numPoisonedBottles - numBads, false);
}

private int[] makeSolution(int[] states) {
ArrayList<Integer> unknownAndBad = new ArrayList<>();
for (int i = 0; i < states.length; i++) {
if (states[i] != good) {
unknownAndBad.add(i);
}
}
int[] ret = new int[unknownAndBad.size()];
for (int i = 0; i < unknownAndBad.size(); i++) {
ret[i] = unknownAndBad.get(i).intValue();
}
return ret;
}

private boolean[] test(BottlesSubmission3[] bottleSets) {
String[] tests = new String[bottleSets.length];
for (int i = 0; i < bottleSets.length; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < bottleSets[i].indexes.length; j++) {
if (j > 0) {
sb.append(",");
}
sb.append(bottleSets[i].indexes[j]);
}
tests[i] = sb.toString();
}
int[] testRes = PoisonTest.useTestStrips(tests);
boolean[] isPoisoned = new boolean[testRes.length];
for (int i = 0; i < isPoisoned.length; i++) {
isPoisoned[i] = testRes[i] == 1;
}
return isPoisoned;
}
}

class BottlesSubmission3 {
int[] indexes;
int numBads;

public BottlesSubmission3(int[] indexes, int numBads, boolean isChecked) {
super();
this.indexes = indexes;
this.numBads = numBads;
}

public boolean isAllGood() {
return numBads <= 0;
}

public boolean isAllBad() {
return numBads >= indexes.length;
}

public double getGoodProbability() {
return 1 - getBadProbability();
}

public double getBadProbability() {
return (double) numBads / indexes.length;
}

}

どの base からどれだけ troop を送るか決める問題で、Codingame の Ghost in the Cell と同じ問題だと思いました。


考えただけのアプローチ


ディープラーニングに任せて、自分は何もしない。
1場面づつ自分でやってみて、評価関数の教師あり学習。


やってみてダメだったアプローチ


SA+モンテカルロシミュレーション



 Approach

序盤


1個か2個の自分の base からできるだけ多く攻撃して、自分のにできたらする。


中盤


Troop の送り先 : 敵の base または自分の base でサイズが200(後で最適化したら300とかの方が良いとでた)以下のもの。
最小費用流で送り主と送り先をmax(2,ceil(送り主数 / 送り先数)):1にマッチングする。
最小費用流のコスト : 送るのにかかる時間 * その base を自分のにしたときの自分の全ての base の (attackT[owner]/2 * 敵から攻撃される確率 )の和


全滅させられそうな時


自分のサイズが 1500 未満の時は、最も近い troop との距離が2以下になったとき、最も遠い base に逃げる。
自分のサイズが 1500 以上の時は、最も近い troop との距離が2以下になったとき、
最も((現在の base )から(行き先の base )までの距離 + (行き先の base )から(行き先の base から最も近い base )までの距離)が大きい base に逃げる。



Approach in English(Google Translate) 



Early stage


I attack as much as possible from one or two my base and I can do it for myself.


Middle stage


Destination of Troop: Size of 200 or less on the base of the enemy or your base (below 300 if you optimized later) or less.
Match the sender and destination to max (2, ceil (number of senders / destinations)): 1 with minimum cost flow.
Cost of minimum cost flow: time to send * Sum of all your base (attackT [owner] * probability of being attacked by enemies) when you make that base yourself


When it is likely to be annihilated


When your size is less than 1500, escape to the furthest base when the distance to the nearest troop becomes 2 or less.
When your size is 1500 or more, when the distance to the nearest troop becomes 2 or less,
Escape to the base with the largest distance (distance from (current base) to (destination base) + (destination base) to (base closest to base of destination).


source code



import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;

//Example scores:
//0) 1657.7984865328203
//1) 90.5096600125314
//2) 1841.1329159343964
//3) 1910.5016049005667
//4) 1876.8965543368483
//5) 1454.4036603297495
//6) 1763.7071055495733
//7) 111.5825278448541
//8) 198.76179380610597
//9) 1747.8803320547408

public class AbstractWars {
private static final TimerManager timer = new TimerManager();
private int numBases;
private int speed;
private Base[] bases;
private double[][] distance;
private int myOwnerValue = 0;

public int init(int[] baseLocations, int speed) {
timer.start("init");
this.numBases = baseLocations.length / 2;
this.speed = speed;

Utils.debug("numBases", numBases, "speed", speed);

bases = new Base[numBases];
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
bases[baseIndex] = new Base();
bases[baseIndex].c = baseLocations[2 * baseIndex + 0];
bases[baseIndex].r = baseLocations[2 * baseIndex + 1];
bases[baseIndex].baseIndex = baseIndex;
}
this.distance = new double[numBases][numBases];
for (int baseIndexFrom = 0; baseIndexFrom < numBases; baseIndexFrom++) {
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
distance[baseIndexFrom][baseIndexTo] = distance(bases[baseIndexFrom], bases[baseIndexTo]);
}
}
timer.stop("init");
return 0;
}

private int getTime(double distance) {
return (int) Math.ceil(distance / speed);
}

ArrayList<Base> myBases = new ArrayList<>();
ArrayList<Base> othersBases = new ArrayList<>();

private int turn;
private int numAIs;

public int[] sendTroops(int[] bases, int[] troops) {
updateInformation(bases, troops);
return solve();
}

private int[][] usedCapacity = new int[102][3000];

private boolean first = true;

private int[] solve() {

if (first && (myBases.size() == 0 || myBases.size() == numBases)) {
Utils.debug("turn", turn, myBases.size() == 0, myBases.size() == numBases);
timer.print();
first = false;
}

if (isMyLastState()) {
return myLastStateHand();
}

if (isFirstTrun()) {
return firstHand();
}

if (isWin()) {
return sendFar();
}

timer.start("normal");

int maxShareOwner = getMaxShareOwnerWithOutMe();
double[] sumExpectedTroopSize = new double[numBases];
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
int currentOwner = bases[baseIndex].owner;
if (bases[baseIndex].owner == myOwnerValue) {
bases[baseIndex].owner = maxShareOwner;
} else {
bases[baseIndex].owner = myOwnerValue;
}

double[] expectedTroopSize = calculateExpectedTroopSize();
for (int baseIndex2 = 0; baseIndex2 < numBases; baseIndex2++) {
if (isMyBase(bases[baseIndex2])) {
sumExpectedTroopSize[baseIndex] += expectedTroopSize[baseIndex2];
}
}

bases[baseIndex].owner = currentOwner;

}

IntArray solution = new IntArray();
int[] baseIndexToMinCostBaseIndex = mincostflow(sumExpectedTroopSize);
for (Base my : myBases) {

int from = my.baseIndex;
int to = baseIndexToMinCostBaseIndex[from];
if (my.size >= 988) {
sendHalf(solution, from, to);
continue;
}

}

updateTurn();
timer.stop("normal");

return solution.toArray();

}

private int[] firstHand() {
timer.start("firstHand");
IntArray solution = new IntArray();
boolean[] used = new boolean[numBases];
for (Base my : myBases) {
if (used[my.baseIndex]) {
continue;
}
for (Base other : othersBases) {
if (canUse(other.baseIndex, turn) && canGetByAll(my, other)) {
sendAll(solution, my.baseIndex, other.baseIndex);
Utils.debug("firstHand", "turn", turn, "growthRate", my.growthRate, other.growthRate);
used[my.baseIndex] = true;
break;
}
}
}

for (Base my : myBases) {
if (used[my.baseIndex]) {
continue;
}
for (Base my2 : myBases) {
if (used[my.baseIndex]) {
continue;
}
if (used[my2.baseIndex]) {
continue;
}
if (my2.baseIndex == my.baseIndex) {
continue;
}
for (Base other : othersBases) {
if (canUse(other.baseIndex, turn) && canGetByAll(my, my2, other)) {
sendAll(solution, my.baseIndex, other.baseIndex);
sendAll(solution, my2.baseIndex, other.baseIndex);
Utils.debug("firstHand", "turn", turn, "growthRate", my.growthRate, my2.growthRate, other.growthRate);
used[my.baseIndex] = true;
used[my2.baseIndex] = true;
break;
}
}
}
}

updateTurn();

timer.stop("firstHand");
return solution.toArray();
}

private boolean canGet(Base my, Base other) {
int myTroopSize = my.size / 2;
int otherSize = other.size;
int maxTime = getTime(distance[my.baseIndex][other.baseIndex]);
for (int time = 1; time <= maxTime; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
if (otherSize > attackT[other.owner]) {
otherSize -= otherSize / 2;
}
}
return myTroopSize > 1 + 1.2 * otherSize;
}

private boolean canGetByAll(Base my, Base other) {
int myTroopSize = my.size - 1;
int otherSize = other.size;
int maxTime = getTime(distance[my.baseIndex][other.baseIndex]);

if (myTroopSize < 1 + 1.2 * otherSize + maxTime * (other.growthRate == 0 ? 3 : other.growthRate)) {
return false;
}

for (int time = 1; time <= maxTime; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
}
return myTroopSize > 1 + 1.2 * otherSize;
}

private boolean canGetByAll(Base my, Base my2, Base other) {
int myTroopSize = my.size - 1;
int my2TroopSize = my2.size - 1;
double otherSize = other.size;
int maxTime = getTime(distance[my.baseIndex][other.baseIndex]);
int maxTime2 = getTime(distance[my2.baseIndex][other.baseIndex]);
if (maxTime > maxTime2) {
{
int swap = maxTime;
maxTime = maxTime2;
maxTime2 = swap;
}
{
int swap = myTroopSize;
myTroopSize = my2TroopSize;
my2TroopSize = swap;
}
}

if (myTroopSize + my2TroopSize < 1 + 1.2 * otherSize + maxTime * (other.growthRate == 0 ? 3 : other.growthRate)) {
return false;
}

for (int time = 1; time <= maxTime; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
}
otherSize -= (1.0 / 1.2) * myTroopSize;
for (int time = maxTime + 1; time <= maxTime2; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
}
return my2TroopSize > 1 + 1.2 * otherSize;
}

private boolean isFirstTrun() {
return turn <= 28;
}

private void sendAll(IntArray solution, int from, int to) {
if (solution.length / 2 + 10 >= numBases) {
return;
}

int size = bases[from].size;
while (size >= 2) {
solution.add(from);
solution.add(to);
size -= size / 2;
}
int time2 = getTime(distance[from][to]);
for (int time = 0; time < time2; time++) {
updateCapacity(to, time);
}
}

private boolean canUse(int baseIndexTo, int turn) {
return usedCapacity[baseIndexTo][turn] == 0;
}

private void updateCapacity(int to, int time) {
usedCapacity[to][turn + time]++;
}

private void sendHalf(IntArray solution, int from, int to) {
solution.add(from);
solution.add(to);
int time2 = getTime(distance[from][to]);
for (int time = 0; time < time2; time++) {
updateCapacity(to, time);
}
}

private int[] mincostflow(double[] sumExpectedTroopSize) {
ArrayList<Base> toBases = new ArrayList<>();
for (int i = 0; i < bases.length; i++) {
if (isMyBase(bases[i])) {
continue;
}
toBases.add(bases[i]);
}

for (Base my : myBases) {
if (my.size < 200) {
toBases.add(my);
}
}

mcf.clear(2 * maxBases + 2);
int s = myBases.size() + toBases.size();
int t = s + 1;

for (int i = 0; i < myBases.size(); i++) {
mcf.addEdge(s, i, 1, 0);
}

for (int i = 0; i < myBases.size(); i++) {
for (int j = 0; j < toBases.size(); j++) {
long cost = (long) (1e2 * (getTime(distance[myBases.get(i).baseIndex][toBases.get(j).baseIndex]) * sumExpectedTroopSize[toBases.get(j).baseIndex]));
if (myBases.get(i).baseIndex == toBases.get(j).baseIndex) {
cost = mcf.INF;
}
if (cost > mcf.INF) {
cost = mcf.INF;
}
mcf.addEdge(i, myBases.size() + j, 1, cost);
}
}
for (int i = 0; i < toBases.size(); i++) {
mcf.addEdge(myBases.size() + i, t, Math.max(2, (int) Math.ceil((double) myBases.size() / toBases.size())), 0);
}
long c = mcf.minCostFlow(s, t, myBases.size());
int[] baseIndexToMinCostBaseIndex = new int[numBases];
Arrays.fill(baseIndexToMinCostBaseIndex, -1);
for (int myBaseIndex = 0; myBaseIndex < myBases.size(); myBaseIndex++) {
ArrayList<Edge> edges = mcf.G.get(myBaseIndex);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int minCostBaseIndex = toBases.get(e.to - myBases.size()).baseIndex;
assert minCostBaseIndex >= 0;
assert minCostBaseIndex < numBases;

baseIndexToMinCostBaseIndex[myBases.get(myBaseIndex).baseIndex] = minCostBaseIndex;

}
}
return baseIndexToMinCostBaseIndex;
}

private int[] attackT = new int[] { 1000, 1000, 1000, 1000, 1000, };

private void updateAttackT() {
for (Troop troop : troops) {
attackT[troop.owner] = Math.min(attackT[troop.owner], 2 * troop.size + 0);
}
}

private double[] calculateExpectedTroopSize() {
double[] expectedTroopSize = new double[numBases];
for (int baseIndexFrom = 0; baseIndexFrom < numBases; baseIndexFrom++) {
if (isMyBase(bases[baseIndexFrom])) {
continue;
}
Base other = bases[baseIndexFrom];

double[] probability = calculateProbability(other);
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
expectedTroopSize[baseIndexTo] += (attackT[other.owner] / 2) * probability[baseIndexTo];
}
}
return expectedTroopSize;
}

private double[] calculateProbability(Base other) {
double[] probability = new double[numBases];
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
if (bases[baseIndexTo].owner == other.owner) {
continue;
}
double d = distance[other.baseIndex][baseIndexTo];
probability[baseIndexTo] += (1.0 / (d * d));
}
double sum = calculateSum(probability);
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
probability[baseIndexTo] /= sum;
}
return probability;
}

private double calculateSum(double[] values) {
double sum = 0;
for (double value : values) {
sum += value;
}
return sum;
}

private int getMaxShareOwnerWithOutMe() {
int[] sumSize = new int[5];
for (int i = 0; i < bases.length; i++) {
sumSize[bases[i].owner] += bases[i].size;
}
for (Troop troop : troops) {
sumSize[troop.owner] += troop.size;
}

int maxIndex = 1;
for (int i = 1; i < sumSize.length; i++) {
if (sumSize[i] > sumSize[maxIndex]) {
maxIndex = i;
}
}

return maxIndex;
}

private boolean isMyLastState() {
timer.start("isMyLastState");
int[] sumSize = new int[5];
for (int i = 0; i < bases.length; i++) {
sumSize[bases[i].owner] += bases[i].size;
}
for (Troop troop : troops) {
sumSize[troop.owner] += troop.size;
}

int sum = 0;
for (int i = 0; i < sumSize.length; i++) {
sum += sumSize[i];
}

for (int i = 1; i < sumSize.length; i++) {
if ((double) sumSize[i] / sum >= 0.7) {
timer.stop("isMyLastState");
return true;
}
}

if ((double) sumSize[myOwnerValue] / sum <= 0.05) {
timer.stop("isMyLastState");
return true;
}

timer.stop("isMyLastState");
return false;
}

private int[] sendFar() {
timer.start("sendFar");
IntArray solution = new IntArray();
for (Base my : myBases) {

if (my.size < 988) {
continue;
}

double maxDistance = -1e9;
int maxi = -1;
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
if (distance[my.baseIndex][baseIndexTo] > maxDistance) {
maxDistance = distance[my.baseIndex][baseIndexTo];
maxi = baseIndexTo;
}
}
int from = my.baseIndex;
int to = maxi;
solution.add(from);
solution.add(to);
int time2 = getTime(distance[from][to]);
for (int time = 0; time < time2; time++) {
updateCapacity(to, time);
}

}

updateTurn();

timer.stop("sendFar");
return solution.toArray();
}

private boolean isWin() {
return othersBases.size() == 0;
}

private double getDistance(int baseIndexFrom, int baseIndexTo) {
if (distance == null) {
distance = new double[numBases][numBases];
for (int baseIndexFrom2 = 0; baseIndexFrom2 < numBases; baseIndexFrom2++) {
for (int baseIndexTo2 = 0; baseIndexTo2 < numBases; baseIndexTo2++) {
int dr = bases[baseIndexFrom2].r - bases[baseIndexTo2].r;
int dc = bases[baseIndexFrom2].c - bases[baseIndexTo2].c;
distance[baseIndexFrom2][baseIndexTo2] = Math.sqrt(dr * dr + dc * dc);
}
}
}
return distance[baseIndexFrom][baseIndexTo];
}

private int[] myLastStateHand() {
timer.start("myLastStateHand");
if (myBases.size() == 0) {
updateTurn();
timer.stop("myLastStateHand");
return new int[] {};
}

int sumMySize = 0;
for (int i = 0; i < bases.length; i++) {
if (bases[i].owner == myOwnerValue) {
sumMySize += bases[i].size;
}

}
for (Troop troop : troops) {
if (troop.owner == myOwnerValue) {
sumMySize += troop.size;
}
}

if (sumMySize > 1500) {

int maxFrom = -1;
int maxTo = -1;
{
double maxDistance = 0;
for (int from = 0; from < numBases; from++) {
for (int to = 0; to < numBases; to++) {
if (to == from) {
continue;
}

double distance = 2 * getDistance(from, to);

double minDistanceFromFrom = 1e9;
double minDistanceFromTo = 1e9;
for (int other = 0; other < numBases; other++) {
if (other != from) {
minDistanceFromFrom = Math.min(minDistanceFromFrom, getDistance(from, other));
}
if (other != to) {
minDistanceFromTo = Math.min(minDistanceFromTo, getDistance(to, other));
}
}
distance += minDistanceFromFrom + minDistanceFromTo;

if (distance > maxDistance) {
maxDistance = distance;
maxFrom = from;
maxTo = to;
}

}
}
}

IntArray solution = new IntArray();
for (Base my : myBases) {
if (isWait(my)) {
continue;
}

double maxDistance = 0;
int maxDistanceBaseIndex = -1;
if (distance[my.baseIndex][maxFrom] > maxDistance) {
maxDistance = distance[my.baseIndex][maxFrom];
maxDistanceBaseIndex = maxFrom;
}
if (distance[my.baseIndex][maxTo] > maxDistance) {
maxDistance = distance[my.baseIndex][maxTo];
maxDistanceBaseIndex = maxTo;
}

assert maxDistanceBaseIndex != -1;

int mySize = my.size;
while (solution.length / 2 < numBases && mySize >= 2) {
solution.add(my.baseIndex);
solution.add(maxDistanceBaseIndex);
int troopSize = mySize / 2;
mySize -= troopSize;
}
}

updateTurn();
timer.stop("myLastStateHand");
return solution.toArray();
} else {
IntArray solution = new IntArray();
for (Base my : myBases) {
if (isWait(my)) {
continue;
}

double maxDistance = 0;
int maxDistanceBaseIndex = -1;
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
if (distance[my.baseIndex][baseIndex] > maxDistance) {
maxDistance = distance[my.baseIndex][baseIndex];
maxDistanceBaseIndex = baseIndex;
}
}

assert maxDistanceBaseIndex != -1;

int mySize = my.size;
while (solution.length / 2 < numBases && mySize >= 2) {
solution.add(my.baseIndex);
solution.add(maxDistanceBaseIndex);
int troopSize = mySize / 2;
mySize -= troopSize;
}
}

updateTurn();
timer.stop("myLastStateHand");
return solution.toArray();
}
}

private boolean isWait(Base my) {
if (my.size >= 988) {
return false;
}

for (Base base : bases) {
if (base.owner == myOwnerValue) {
continue;
}

int dx = base.c - my.c;
int dy = base.r - my.r;
double distance = Math.sqrt(dx * dx + dy * dy);
if (getTime(distance) <= 2) {
return false;
}
}
for (Troop troop : troops) {
if (troop.owner == myOwnerValue) {
continue;
}

int dx = troop.c - my.c;
int dy = troop.r - my.r;
double distance = Math.sqrt(dx * dx + dy * dy);
if (getTime(distance) <= 2) {
return false;
}
}
return true;
}

private int maxBases = 100;
private MinCostFlow2 mcf = new MinCostFlow2(2 * maxBases + 2);

private double distance(int dx, int dy) {
return Math.sqrt(dx * dx + dy * dy);
}

private double distance(Base base0, Base base1) {
return Math.sqrt(squaredDistance(base0, base1));
}

private int squaredDistance(Base base0, Base base1) {
int dr = base0.r - base1.r;
int dc = base0.c - base1.c;
int a = dr * dr + dc * dc;
return a;
}

private void updateTurn() {
turn++;
}

private void updateInformation(int[] bases, int[] troops) {
timer.start("updateInformation");
updateBaseInformation(bases);
updateTroopInformation(troops);

{
HashSet<Integer> playerIndexSet = new HashSet<>();
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
playerIndexSet.add(this.bases[baseIndex].owner);
numAIs = Math.max(numAIs, this.bases[baseIndex].owner + 1);
}
}

myBases.clear();
othersBases.clear();
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
if (isMyBase(bases, baseIndex)) {
myBases.add(this.bases[baseIndex]);
} else {
othersBases.add(this.bases[baseIndex]);
}
}

updateAttackT();
timer.stop("updateInformation");
}

private int[][] baseOwner = new int[2000][100];
private int[][] baseSize = new int[2000][100];

private void updateBaseInformation(int[] bases) {
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
this.bases[baseIndex].owner = bases[2 * baseIndex + 0];
this.bases[baseIndex].size = bases[2 * baseIndex + 1];

baseOwner[turn][baseIndex] = this.bases[baseIndex].owner;
baseSize[turn][baseIndex] = this.bases[baseIndex].size;
}

if (turn - 1 >= 0) {
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
if (baseOwner[turn][baseIndex] != baseOwner[turn - 1][baseIndex]) {
continue;
}
int growthRate = baseSize[turn][baseIndex] - baseSize[turn - 1][baseIndex] - baseSize[turn - 1][baseIndex] / 100;
if (!(growthRate >= 1 && growthRate <= 3)) {
continue;
}
this.bases[baseIndex].growthRate = growthRate;
}
}
}

private ArrayList<Troop> troops = new ArrayList<>();

private void updateTroopInformation(int[] troops) {
this.troops.clear();
int numTroops = troops.length / 4;
for (int troopIndex = 0; troopIndex < numTroops; troopIndex++) {
Troop troop = new Troop();
troop.owner = troops[4 * troopIndex + 0];
troop.size = troops[4 * troopIndex + 1];
troop.c = troops[4 * troopIndex + 2];
troop.r = troops[4 * troopIndex + 3];
this.troops.add(troop);
}
}

private boolean isMyBase(Base base) {
return base.owner == 0;
}

private boolean isMyBase(int[] bases, int i) {
return bases[2 * i] == 0;
}

public static void main(String[] args) {
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
AbstractWars aw = new AbstractWars();

int N = Integer.parseInt(reader.readLine());
int[] baseLocations = new int[N];
for (int i = 0; i < N; i++) {
baseLocations[i] = Integer.parseInt(reader.readLine());
}
int speed = Integer.parseInt(reader.readLine());
int retInit = aw.init(baseLocations, speed);
System.out.println(retInit);
System.out.flush();

for (int st = 0; st < 2000; st++) {
String line = reader.readLine();
if (line == null) {
break;
}
int B = Integer.parseInt(line);
int[] bases = new int[B];
for (int i = 0; i < B; i++) {
bases[i] = Integer.parseInt(reader.readLine());
}
int T = Integer.parseInt(reader.readLine());
int[] troops = new int[T];
for (int i = 0; i < T; i++) {
troops[i] = Integer.parseInt(reader.readLine());
}

int[] ret = aw.sendTroops(bases, troops);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
}
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Base {

public int growthRate;
public int owner;
public int size;
public int r;
public int c;
public int baseIndex;
}

class Troop {

public int owner;
public int size;
public int r;
public int c;

}

class RealAI {
SecureRandom rnd;
int attackT;
double locality;
int B;
int owner;
int[] baseX, baseY;

RealAI(long seed, int own) {
try {
rnd = SecureRandom.getInstance("SHA1PRNG");
} catch (Exception e) {
}
rnd.setSeed(seed);
owner = own;
attackT = 1000 / 2 + rnd.nextInt(1000 / 2);
locality = rnd.nextDouble() * 2 + 1;
}

int init(int[] baseLocations, int speed) {
B = baseLocations.length / 2;
baseX = new int[B];
baseY = new int[B];
for (int i = 0; i < B; ++i) {
baseX[i] = baseLocations[2 * i];
baseY[i] = baseLocations[2 * i + 1];
}
return 0;
}

ArrayList<Integer> others;

int getRandomBase(int sourceInd) {
double[] probs = new double[others.size()];
double sp = 0;
for (int i = 0; i < others.size(); ++i) {
int ind = others.get(i).intValue();
probs[i] = Math.pow(1.0 / (Math.pow(baseX[sourceInd] - baseX[ind], 2) + Math.pow(baseY[sourceInd] - baseY[ind], 2)), locality);
sp += probs[i];
}

double r = rnd.nextDouble() * sp;
double s = 0;
for (int i = 0; i < others.size(); ++i) {
s += probs[i];
if (s >= r)
return others.get(i).intValue();
}
return others.get(others.size() - 1).intValue();
}

int[] sendTroops(int[] bases, int[] troops) {
others = new ArrayList<Integer>();
for (int i = 0; i < B; ++i)
if (bases[2 * i] != owner)
others.add(i);
if (others.size() == 0) {
return new int[0];
}

ArrayList<Integer> att = new ArrayList<Integer>();
for (int i = 0; i < B; ++i) {
if (bases[2 * i] == owner && bases[2 * i + 1] > attackT) {
att.add(i);
att.add(getRandomBase(i));
}
}
int[] ret = new int[att.size()];
for (int i = 0; i < att.size(); ++i)
ret[i] = att.get(i).intValue();
return ret;
}
}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

public boolean isEmpty() {
return length == 0;
}

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class MinCostFlow2 {
final long INF = (long) 1e15;
ArrayList<ArrayList<Edge>> G;

public MinCostFlow2(int v) {
G = new ArrayList<ArrayList<Edge>>();
for (int i = 0; i < v; i++) {
G.add(new ArrayList<Edge>());
}
dist = new long[v];
prevv = new int[v];
preve = new int[v];
}

public void clear(int v) {
G = new ArrayList<ArrayList<Edge>>();
for (int i = 0; i < v; i++) {
G.add(new ArrayList<Edge>());
}
dist = new long[v];
prevv = new int[v];
preve = new int[v];
}

public void addEdge(int from, int to, int cap, long cost) {
G.get(from).add(new Edge(to, cap, cost, G.get(to).size()));
G.get(to).add(new Edge(from, 0, -cost, G.get(from).size() - 1));
}

private long[] dist;
private int[] prevv;
private int[] preve;

public int minCostFlow(int s, int t, int f) {
int res = 0;
while (f > 0) {
Arrays.fill(dist, INF);
dist[s] = 0;

for (;;) {
boolean update = false;

for (int v = 0; v < dist.length; v++) {
if (dist[v] >= INF) {
continue;
}
for (int i = 0; i < G.get(v).size(); i++) {
Edge e = G.get(v).get(i);
if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}

if (!update) {
break;
}
}
if (dist[t] >= INF) {
return -1;
}

int d = f;
for (int v = t; v != s; v = prevv[v]) {
d = Math.min(d, G.get(prevv[v]).get(preve[v]).cap);
}

f -= d;
res += d * dist[t];

for (int v = t; v != s; v = prevv[v]) {
Edge e = G.get(prevv[v]).get(preve[v]);
e.cap -= d;
G.get(v).get(e.rev).cap += d;
}

}

return res;
}
}

class Edge {
int to;
int cap;
int rev;
long cost;

public Edge(int to, int cap, long cost, int rev) {
this.to = to;
this.cap = cap;
this.rev = rev;
this.cost = cost;
}
}

class Point implements Comparable<Point> {

public int x;
public int y;

public Point() {
this(0, 0);
}

public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}

public Point add(Point point) {
return new Point(x + point.x, y + point.y);
}

public Point subtract(Point point) {
return new Point(x - point.x, y - point.y);
}

public Point multiply(int a) {
return new Point(a * x, a * y);
}

public Point divide(int a) {
return new Point(x / a, y / a);
}

public double cross(Point point) {
return x * point.y - y * point.x;
}

public Point operator(Point a) {
return new Point(x * a.x - y * a.y, x * a.y + y * a.x);
}

@Override
public int compareTo(Point o) {
if (x == o.x) {
if (y == o.y) {
return 0;
} else if (y < o.y) {
return -1;
} else {
return 1;
}
} else if (x < o.x) {
return -1;
} else {
return 1;
}
}

@Override
public String toString() {
return "(" + x + "," + y + ")";
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

}

class GeometryUtils {
private GeometryUtils() {
}

private static final int grahamscanCcw(Point p1, Point p2, Point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

public static final Point[] grahamscan(Point[] p) {
int N = p.length;
Point[] points = new Point[N + 1];
for (int i = 1; i < points.length; i++) {
points[i] = p[i - 1];
}
for (int i = 2; i < points.length; i++) {
if (points[i].y < points[1].y || (points[i].y == points[1].y && points[i].x > points[1].x)) {
Point swap = points[1];
points[1] = points[i];
points[i] = swap;
}
}
Arrays.sort(points, 2, points.length, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
double theta1 = Math.atan2(o1.y - points[1].y, o1.x - points[1].x);
double theta2 = Math.atan2(o2.y - points[1].y, o2.x - points[1].x);
if (theta1 < theta2) {
return -1;
}
if (theta1 > theta2) {
return 1;
}
double distance1 = MathUtils.euclideanDistance(o1.y - points[1].y, o1.x - points[1].x, 0, 0);
double distance2 = MathUtils.euclideanDistance(o2.y - points[1].y, o2.x - points[1].x, 0, 0);
if (distance1 < distance2) {
return -1;
}
if (distance1 > distance2) {
return 1;
}
return 0;
}
});
points[0] = points[N];
int M = 1;
for (int i = 2; i < points.length; i++) {
while (grahamscanCcw(points[M - 1], points[M], points[i]) <= 0) {
if (M > 1) {
M -= 1;
continue;
} else if (i == N) {
break;
} else {
i += 1;
}
}
M += 1;
{
Point swap = points[M];
points[M] = points[i];
points[i] = swap;
}
}

Point[] convexHull = new Point[M];
for (int i = 0; i < convexHull.length; i++) {
convexHull[i] = points[i];
}
return convexHull;
}

public static final boolean strictInsideConvexPolygon(Point p, Point[] ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.length; i++) {
int j = (i + 1) % ps.length;

int ccw = ccw(ps[i], ps[j], p);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean insideConvexPolygon(Point[] p, Point[] ps) {
for (int i = 0; i < p.length; i++) {
if (!insideConvexPolygon(p[i], ps)) {
return false;
}
}
return true;
}

public static final boolean insideConvexPolygon(Point p, Point[] ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.length; i++) {
int j = (i + 1) % ps.length;

int ccw = ccw(ps[i], ps[j], p);
if (ccw == 0) {
return true;
}
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min >= 0) {
return true;
}
if (max <= 0) {
return true;
}

return !true;
}

public static final boolean insideConvexPolygon(Point p, ArrayList<Point> ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.size(); i++) {
int j = (i + 1) % ps.size();

int ccw = ccw(ps.get(i), ps.get(j), p);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min >= 0) {
return true;
}
if (max <= 0) {
return true;
}

return !true;
}

public static final boolean strictInsideConvexPolygon(Point p, ArrayList<Point> ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.size(); i++) {
int j = (i + 1) % ps.size();

int ccw = ccw(ps.get(i), ps.get(j), p);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean isConvexPolygon(Point[] ps) {
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.length; i++) {
int j = (i + 1) % ps.length;
int k = (i + 2) % ps.length;

int ccw = ccw(ps[i], ps[j], ps[k]);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean isConvexPolygon(ArrayList<Point> ps) {
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.size(); i++) {
int j = (i + 1) % ps.size();
int k = (i + 2) % ps.size();

int ccw = ccw(ps.get(i), ps.get(j), ps.get(k));
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean inside(Point[] tests, Point[] points) {
for (int i = 0; i < tests.length; i++) {
if (!inside(tests[i], points)) {
Utils.debug("tests[i]", tests[i], "points", points);
return false;
}
}
return true;
}

public static final boolean inside(Point testPoint, Point[] points) {
if (onBorder(testPoint, points)) {
return true;
}

return inside0(testPoint, points);
}

public static final boolean strictInside(Point testPoint, Point[] points) {
if (onBorder(testPoint, points)) {
return false;
}

return inside0(testPoint, points);
}

private static boolean onBorder(Point testPoint, Point[] points) {
for (int i = 0; i < points.length; i++) {
if (ccw(points[i], points[(i + 1) % points.length], testPoint) == 0) {
return true;
}
}
return false;
}

private static final boolean inside0(Point testPoint, Point[] points0) {
Point[] points = new Point[points0.length];
{
int mini = 1;
for (int i = 0; i < points0.length; i++) {
if (points0[i].y < points0[mini].y) {
mini = i;
} else if (points0[i].y == points0[mini].y && points0[i].x < points0[mini].x) {
mini = i;
}
}
for (int i = 0; i < points.length; i++) {
points[(1 + i) % points.length] = points0[(mini + i) % points.length];
}
}

int i = 0;
int count = 0;
int j = 0;

Line testLine = new Line(new Point(testPoint.x, testPoint.y), new Point(testPoint.x, testPoint.y));
testLine.p2.x = (int) 1e5;

int n = points.length;
Point[] newps = new Point[n + 2];
for (int k = 0; k < n; k++) {
newps[k] = points[k];
}
newps[n] = newps[0];
newps[n + 1] = newps[1];

for (i = 1; i <= n; i++) {
if (ccw(testLine.p1, testLine.p2, newps[i]) == 0) {
continue;
}
if (i == j + 1) {
if (intersect(new Line(newps[i], newps[j]), testLine)) {
count++;
}
} else {
if (ccw(testLine.p1, testLine.p2, newps[i]) * ccw(testLine.p1, testLine.p2, newps[j]) < 0) {
count++;
}
}
j = i;
}
return (count & 1) == 1;
}

public static final boolean intersect(Line l1, Line l2) {
return (ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2) <= 0) && (ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2) <= 0);
}

public static final double thetaRobertSedgewick(Point p1, Point p2) {
int dx = p2.x - p1.x;
int ax = Math.abs(dx);
int dy = p2.y - p1.y;
int ay = Math.abs(dy);
double t = (ax + ay == 0) ? 0 : (double) dy / (double) (ax + ay);
if (dx < 0) {
t = 2 - t;
} else if (dy < 0) {
t = 4 + t;
}
return Math.toRadians(t * 90.0);
}

public static final int ccw(Point p0, Point p1, Point p2) {
int dx1 = p1.x - p0.x;
int dy1 = p1.y - p0.y;
int dx2 = p2.x - p0.x;
int dy2 = p2.y - p0.y;
if (dx1 * dy2 > dy1 * dx2) {
return 1;
}
if (dx1 * dy2 < dy1 * dx2) {
return -1;
}
if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) {
return -1;
}
if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) {
return 1;
}
return 0;
}
}

class Line {
public Point p1;
public Point p2;

public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}

class MathUtils {
private MathUtils() {
}

public static final double earthDistance(double latitude0, double longitude0, double latitude1, double longitude1, double earthRadius) {
double deltaLon = Math.abs(longitude0 - longitude1);
if (deltaLon > 180) {
deltaLon = 360 - deltaLon;
}
deltaLon = Math.toRadians(deltaLon);
longitude0 = Math.toRadians(longitude0);
longitude1 = Math.toRadians(longitude1);
latitude0 = Math.toRadians(latitude0);
latitude1 = Math.toRadians(latitude1);
double e = Math.cos(latitude0) * Math.sin(deltaLon);
double e2 = Math.cos(latitude1) * Math.sin(latitude0) - Math.sin(latitude1) * Math.cos(latitude0) * Math.cos(deltaLon);
return earthRadius * Math.atan2(Math.sqrt(e * e + e2 * e2), Math.sin(latitude1) * Math.sin(latitude0) + Math.cos(latitude1) * Math.cos(latitude0) * Math.cos(deltaLon));
}

public static final double transitTime(double latitude0, double longitude0, double latitude1, double longitude1, double earthRadius) {
double highSlope = 60.0 / 122.0;
double lowSlope = 53.3 / 120.0;
double meanSlope = 60.0 * (highSlope + lowSlope) / 2.0;
double earthCircumference = 2.0 * Math.PI * earthRadius;
double earthDistance = earthDistance(latitude0, longitude0, latitude1, longitude1, earthRadius);
return (earthDistance / earthCircumference) * 360.0 * meanSlope;
}

public static final int euclideanDistanceSquared(int x0, int y0, int x1, int y1) {
return MathUtils.euclideanDistanceSquared(x1 - x0, y1 - y0);
}

public static final int euclideanDistanceSquared(int dx, int dy) {
return dx * dx + dy * dy;
}

public static final long euclideanDistanceSquared(long dx, long dy) {
return dx * dx + dy * dy;
}

public static final double euclideanDistance(double r1, double c1, double r2, double c2) {
double deltaR = r2 - r1;
double deltaC = c2 - c1;
return Math.sqrt(deltaR * deltaR + deltaC * deltaC);
}

public static final double manhattanDistance(double r1, double c1, double r2, double c2) {
double deltaR = r2 - r1;
double deltaC = c2 - c1;
return Math.abs(deltaR) + Math.abs(deltaC);
}

public static final double euclideanDistance(double[] a, double[] b) {
assert a.length == b.length;

int n = a.length;

double sum = 0;
for (int i = 0; i < n; i++) {
double delta = a[i] - b[i];
sum += delta * delta;
}
return Math.sqrt(sum);
}

public static final double calculateEuclideanNorm(double[] a) {
double euclideanNorm = 0;
for (int i = 0; i < a.length; i++) {
euclideanNorm += a[i] * a[i];
}
euclideanNorm = Math.sqrt(euclideanNorm);
return euclideanNorm;
}

}

class TimerManager {
HashMap<String, Timer> map = new HashMap<>();

public void start(String id) {
if (map.get(id) == null) {
map.put(id, new Timer());
}
Timer timer = map.get(id);
timer.setDescription(id);
timer.start();
}

public void stop(String id) {
if (map.get(id) == null) {
map.put(id, new Timer());
}
Timer timer = map.get(id);
timer.setDescription(id);
timer.stop();
}

public void print() {
ArrayList<Timer> timers = new ArrayList<>();
timers.addAll(map.values());
Collections.sort(timers);
for (int i = 0; i < timers.size(); i++) {
timers.get(i).print();
}
}
}

class Timer implements Comparable<Timer> {
private double time;
private long start;
private long stop;
private int count;
private String description;
private boolean isRunning;

public Timer() {
reset();
}

@Override
public int compareTo(Timer o) {
if (time < o.time) {
return 1;
}
if (time > o.time) {
return -1;
}
return 0;
}

public int getCount() {
return count;
}

public String getDescription() {
return description;
}

public long getStart() {
return start;
}

public long getStop() {
return stop;
}

public double getTime() {
return time;
}

public boolean isRunning() {
return isRunning;
}

public void print() {
if (count > 0) {
Utils.debug(String.format("time, %10s, count, %10d, time/count, %12.9f, %s", TimeManager.toString(time), count, time / count, description));
}
}

public void reset() {
time = 0;
start = 0;
stop = 0;
count = 0;
isRunning = false;
}

public void setDescription(String description) {
assert this.description == null || this.description.equals(description);
if (this.description == null) {
this.description = description;
}
}

public void start() {
assert isRunning == false;
isRunning = true;
start = System.nanoTime();
}

public void stop() {
assert isRunning == true;
stop = System.nanoTime();
count++;
time += (stop - start) * 1e-9;
isRunning = false;
}
}

class TimeManager {
private long start;
private int count;

public TimeManager() {
init();
}

public int getCount() {
return count;
}

public double getSecond() {
count++;
return (System.nanoTime() - start) * 1e-9;
}

public long getTime() {
count++;
return System.nanoTime() - start;
}

public void init() {
init(System.nanoTime());
}

public void init(long start) {
this.start = start;
count = 0;
}

public String toString() {
return toString(getSecond());
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}



このページのトップヘ