Pagini recente » Cod sursa (job #3304710) | Cod sursa (job #2299473) | Monitorul de evaluare | Cod sursa (job #2380462) | Cod sursa (job #3359056)
/*
Ehhhh, cam pierdere de timp
A parut interesanta, dar doar a parut...
*/
/*
Observatia 1: dublul ariei unui poligon cu punctele x[i], y[i] date in ordinea trigonometrica este
\sum_i x[i] * y[i + 1] - y[i] * x[i + 1], iar i + 1 este 1 pentru i = n (adica ciclic)
Pentru mai multe detalii, vezi https://www.infoarena.ro/problema/aria
De aici e over problema, deoarece trebuie sa calculezi suma asta pentru toate submultimiile punctelor de acolo
Submultimile sunt determinate unic de indicii punctelor, iar functia de mai sus este o functie de 2
puncte, deci ne dam seama ca suma e dependenta de perechi de puncte ce apar in submultime
(mai exact de indicii lor)
Exista 2 tipuri de contributii:
1) contributie i < j. Adica ai punct[i] - punct[j] unul dupa altul in poligonul considerat
2) contributie j > i. Adica ai punct[j] - punct[i] unul dupa altul in poligon. Asta se intampla doar la ultimul
pas cand te intorci la primul punct, deci i este de fapt primul punct din poligon, iar j - ultimul
Suma de mai sus deci devine
\sum_{i < j} (x[i] * y[j] - y[i] * x[j]) * ((de cate ori apare in forma i < j) - (de cate ori apare in forma j > i))
(de cate ori apare in forma i < j) e doar 2^(i - 1) * 2^(n - j), deoarece te intereseaza doar cate submultimi
contin aceasta pereche consecutiv. Consecutiv inseamna ca nu e nimeni intre ei, fiind sortata submultimea,
deci raman doar cei mai mari si cei mai mici ce pot sa apara sa nu, deci fix produsul ala.
(de cate ori apare in forma i > j) e doar 2^(j - i - 1), deoarece i e primul, j e ultimul, asa ca toate
punctele ce pot aparea vor avea indici intre i si j exclusiv. Sunt doar j - i - 1 intre, deci 2^(j - i - 1)
submultimi
Daca trantesti 2 for-uri cu formula de mai sus iei 60p.
*/
/*
Pentru maxim, trebuie sa scoti pixul si hartia si sa spargi contributia in partea lui i si partea lui j,
ca la orice problema de tehnica contributiei.
Am sa fac calculele, insa fara indici ca sa n-o lungesc prea mult
Avem doar
\sum_{i < j} (x[i] y[j] - x[j] y[i]) (2^(i + n - j - 1) - 2^(j - i - 1))
2^(n-1) \sum_{i < j} (x[i] y[j] - x[j] y[i]) 2^(i - j) - \sum_{i < j} (x[i] y[j] - x[j] y[i]) 2^(j - i - 1)
2^(n-1) \sum_i 2^i \sum_j (x[i] y[j] - x[j] y[i]) 2^(-j) - \sum_i 2^(-i) \sum_j (x[i] y[j] - x[j] y[i]) 2^(j - 1)
2^(n-1) \sum_i 2^i (x[i] \sum_j y[j] 2^(-j) - y[i] \sum_j x[j] 2^(-j))
-\sum_i 2^(-i) (x[i] \sum_j y[j] 2^(j - 1) - y[i] \sum_j x[j] 2^(j - 1))
2^(n-1) (\sum_i 2^i x[i] (\sum_j y[j] 2^(-j)) - \sum_i 2^i y[i] (\sum_j x[j] 2^(-j)))
-(\sum_i 2^(-i) x[i] (\sum_j y[j] 2^(j - 1)) - \sum_i 2^(-i) y[i] (\sum_j x[j] 2^(j - 1)))
Sumele cu j sunt doar niste sume partiale pe sufix, asta dupa ce precalculezi 2^i si 2^(-i).
Teoretic poti sa nu precalculezi inversele modulare daca distribui in prima suma n la -j si atunci
e iarasi putere a lui 2, iar in a 2-a daca inmultesti si imparti prin 2^n (ma rog, cred ca tot
va trebui sa faci un invers cel putin)
Sumele partiale pe sufix se pot face si fara a le retine daca faci suma de la coada la cap, adica
daca construiesti intr-o singura variabila tot (sau ma rog, poti si de la stanga la dreapta daca
scazi la fiecare pas contributia pozitiei i)
Complexitate O(N)
*/
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
const int MOD = 1e9 + 7;
const int INV2 = 500000004;
struct point
{
int x, y;
point() {}
};
struct math
{
vector <int> pow2;
vector <int> inv2;
int dim;
math(int n)
{
dim = n;
pow2.resize(n);
inv2.resize(n);
pow2[0] = 1;
inv2[0] = 1;
for (int i = 1; i < n; i++)
{
pow2[i] = 1LL * pow2[i - 1] * 2 % MOD;
inv2[i] = 1LL * inv2[i - 1] * INV2 % MOD;
}
}
int _2to(int n)
{
assert(0 <= n and n < dim);
return pow2[n];
}
int _inv2to(int n)
{
assert(0 <= n and n < dim);
return inv2[n];
}
};
vector <point> read_polygon()
{
ifstream in("ultrapoligon.in");
int n, i;
in >> n;
vector <point> poly;
poly.resize(n);
for (i = 0; i < n; i++)
in >> poly[i].x >> poly[i].y;
in.close();
return poly;
}
int compute_areas(vector <point> &polygon)
{
int i, inc_sum, dec_sum;
math _(polygon.size() + 1);//voiam initial s-o numesc formulae, insa devenea foarte laborios codul
//efectiv instantiam matematica de care avem nevoie, adica doar niste puteri
inc_sum = 0;
int sum_x = 0; //suma din x[i] * 2^-i
int sum_y = 0; //suma din y[i] * 2^-i
for (i = polygon.size() - 1; i >= 1; i--)
{
sum_x = (sum_x + 1LL * polygon[i].x * _._inv2to(i) % MOD) % MOD;
sum_y = (sum_y + 1LL * polygon[i].y * _._inv2to(i) % MOD) % MOD;
inc_sum = (inc_sum + 1LL * _._2to(i - 1) * polygon[i - 1].x % MOD * sum_y % MOD) % MOD;
inc_sum = (inc_sum - 1LL * _._2to(i - 1) * polygon[i - 1].y % MOD * sum_x % MOD + MOD) % MOD;
}
inc_sum = 1LL * inc_sum * _._2to(polygon.size() - 1) % MOD;
dec_sum = 0;
sum_x = 0; //suma din x[i] * 2^(i-1)
sum_y = 0; //suma din y[i] * 2^(i-1)
for (i = polygon.size() - 1; i >= 1; i--)
{
sum_x = (sum_x + 1LL * polygon[i].x * _._2to(i - 1) % MOD) % MOD;
sum_y = (sum_y + 1LL * polygon[i].y * _._2to(i - 1) % MOD) % MOD;
dec_sum = (dec_sum + 1LL * _._inv2to(i - 1) * polygon[i - 1].x % MOD * sum_y % MOD) % MOD;
dec_sum = (dec_sum - 1LL * _._inv2to(i - 1) * polygon[i - 1].y % MOD * sum_x % MOD) % MOD;
}
return (inc_sum - dec_sum + MOD) % MOD;
}
void output_answer(int answer)
{
ofstream out("ultrapoligon.out");
out << answer;
out.close();
}
int main()
{
vector <point> poly = read_polygon();
output_answer(compute_areas(poly));
}