/**
Observam ca pentru a acoperi un punct cu un dreptunghi cu centrul
in origine acest dreptunghi va avea un colt in punctul dat.
Pentru a acoperi doua puncte cu un dreptunghi, fie un punct este complet inclus
in dreptunghiul pentru elalalt punct (cand atat x-ul cat si y-ul sau sunt mai mici decat coordonatele corespunzatoare de lacelalalt punct)
fie punctul al doilea face sa se laturile dreptunghiului celuilalt punct.
Ambele puncte vor fi oricum pe laturile dreptunghiului
|
-----|-*---
| | |
| | *
| | |
--------------------------
| | |
| | |
| | |
-----------
|
Sa vedem ce se intampla daca multiplicam in 4
(din x,y mai obtinem pe x,-y -x,y si -x,-y )
Figura noastra
|
---*-|-*---
| | |
* | *
| | |
--------------------------
| | |
* | *
| | |
---*---*---
|
Daca pentru fiecare punct consideram dteptunghiul cu varfurile in
"cele 4 puncte ale sale", ajungem la ceva de genul:1
|
*-|-*
| | |
*--|-|-|--*
| | | | |
--------------------------
| | | | |
*----|----*
| | |
*---*
|
Dupa ce obtinem aceste dreptunghiuri, noi le vom elimina pe cele care sunt complet
incluse in altele (un dreptunghi este complet inclus in altul daca
are dimensiunile mai mici sau egale decat cele corespunzatoare ale celuilalt)
Obtinem deci dreptunghiurile in forma de "scara" pe un cadran.
Concret, pentru a face asta, baleiem cu un x de la dreapta la stanga
si la fiecare x distinct aflam y minim si y maxim doar.
Odata obtinuta aceasta figura observam ca solutia este formata doar din astfel de dreptunghiuri (in afara lor nu mai sunt puncte)
sau din dreptunghiuri formate unind mai multe VECINE dintre cele obtinute
(noi le consideram ordonate crescator dupa o dimensiune, deci automat descrescator dupa cealalta - mod in care le obtinem la baleiere).
vom face o dinamica dp[i] = suma minima sa acoperim primele i dreptunghiuri
pentru calculul lui dp[i] vom varia un j inapoi, gandindu-ne ca acoperim toate dreptunghiurile
de la i la j (ultimele) cu unulsingur si apoi dinamica pentru cele din fata pozitiei j
deci dp[i] = min ( dp[j-1] + aria (j..i) ).
Dar aria de la j la i se obtine inmultind maxim dintre y de i si y de j cu maxim dintre x-ii celor doua dreptunghiuri, deci in o(1).
Avem asadar timp de calcul de ordin n^2, unde n este numarulde puncte date.
**/
#include <iostream>
#include <set>
using namespace std;
struct elem {
long long x;
long long y;
};
struct dreptunghi {
long long dimx;
long long dimy;
};
set<pair<long long, long long> > s;
elem v[20010];
dreptunghi d[20010];
long long dp[20010];
long long n, k, i, x, y, minim, maxim, sol;
int main () {
cin>>n;
for (i=1;i<=n;i++) {
cin>>x>>y;
s.insert(make_pair(x, y));
s.insert(make_pair(-x, y));
s.insert(make_pair(x, -y));
s.insert(make_pair(-x, -y));
}
n = 0;
for (set<pair<long long, long long> >::iterator it = s.begin(); it!=s.end(); it++) {
v[++n].x = it->first;
v[n].y = it->second;
}
minim = v[1].y;
maxim = v[1].y;
for (i=2;i<=n;i++) {
if (v[i].x >= 0)
break;
if (v[i].x == v[i-1].x) {
maxim = max(maxim, v[i].y);
minim = min(minim, v[i].y);
} else {
if (k == 0 || maxim-minim > d[k].dimy) {
d[++k].dimx = -v[i-1].x*2;
d[k].dimy = maxim - minim;
}
maxim = v[i].y;
minim = v[i].y;
}
}
if (k == 0 || maxim-minim > d[k].dimy) {
d[++k].dimx = -v[i-1].x * 2;
d[k].dimy = maxim - minim;
}
for (i=1;i<=k;i++) {
dp[i] = d[1].dimx*d[i].dimy;
for (long long j=i;j>=1;j--) {
dp[i] = min(dp[i], dp[j-1] + d[j].dimx * d[i].dimy);
}
}
cout<<dp[k];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
504 KB |
Output is correct |
| 8 |
Correct |
4 ms |
632 KB |
Output is correct |
| 9 |
Correct |
10 ms |
1404 KB |
Output is correct |
| 10 |
Correct |
16 ms |
2040 KB |
Output is correct |
