#include #define PRVOCISLO 1000000007 typedef long long int ll; // Funkce spočítá počet černých čtverečků v obdélníku s levým dolním rohem v 0,0 // a pravým horním rohem v x,y ll od_pocatku(ll x, ll y) { // Vzhledem k použití se může stát, že x nebo y je záporné, takové případy // je lepší vyřídit hned (v takovém obdélníku je 0 černých čtverečků) if (x < 0 || y < 0) return 0; // Vyjádříme si, která souřadnice je větší (max) a která menší (min) ll min = (x < y ? x : y); ll max = (x > y ? x : y); // Nejprve vyřešíme čtverec 0,0 -- min,min ll cernych_vln = ((min + 1) / 2) % PRVOCISLO; // Počet černých vln ve čtverci // Počet čtverečků spočítáme dle vzorce: // 3 + 7 + 11 + ... + (4*n - 1) = 2n^2 + n ll ctverec = (2 * cernych_vln * cernych_vln + cernych_vln) % PRVOCISLO; // Dále spočítáme počet černých čtverečků v obdélníku 0,min -- max,min // (nebo ekvivalentne min,0 -- min,max) // Obdélník chápeme tak, že máme vedle sebe střídavě bílé a černé sloupce // tyto sloupce jsou vysoké "výška" a je jich "šířka". "Černá šířka" // je pak počet černých sloupců ll cerna_sirka_obdelnika = (max - min) / 2; // Každý druhý je černý if (~min & max & 1) // pokud je však min liché a max sudé... ++cerna_sirka_obdelnika; // tak začínáme i končíme černým sloupcem cerna_sirka_obdelnika %= PRVOCISLO; ll vyska_obdelnika = (min + 1) % PRVOCISLO; ll obdelnik = vyska_obdelnika * cerna_sirka_obdelnika; return (obdelnik + ctverec) % PRVOCISLO; } int main() { ll prvni_x, prvni_y, druhy_x, druhy_y; scanf("%lld%lld%lld%lld", &prvni_x, &prvni_y, &druhy_x, &druhy_y); ll velky = od_pocatku(druhy_x, druhy_y); ll stredni1 = od_pocatku(druhy_x, prvni_y - 1); ll stredni2 = od_pocatku(prvni_x - 1, druhy_y); ll maly = od_pocatku(prvni_x - 1, prvni_y - 1); // Výsledek po odečtení stredni1 a stredni2 může být záporný (dokonce // menší než PRVOCISLO, ale ne nez 2 * PRVOCISLO). Nejjednodušší // způsob jak dostat modulo PRVOCISLO je PRVOCISLO dvakrát přičíst // před modulením printf("%lld\n", ((velky - stredni1 - stredni2 + maly) + 2 * PRVOCISLO) % PRVOCISLO); return 0; }