1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 `#include #include #include #define zak 1000000 using namespace std; int x1,x2,y1,y2,X,Y,n, W, H; vector, pair > > plotX, plotY; long long pocz[zak], dp[zak], best[zak]; long long line[zak], kon[zak]; bool isBegin[zak]; long long WYN; void BEST(int pp, int kp) { //printf("BEST %d %d (%d - %d)\n", pp, kp, line[pp], line[kp]); long long wyn = 0; for(int i = pp + 1; i <= kp;) { wyn += line[i] - line[i - 1]; WYN = max(WYN, wyn); //printf("from %d to %d\n", line[i-1], line[i]); if(isBegin[i]) { //printf("New wall\n"); BEST(i, min(kon[i], (long long)kp)); //printf("Out\n"); i = kon[i] + 1; } else { wyn = 0; i++; } } } int main() { scanf("%d%d%d\n", &n, &X, &Y); for(int i=1;i<=n;i++) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); plotX.emplace_back(make_pair(x1, 1), make_pair(-x2, i)); plotY.emplace_back(make_pair(y1, 1), make_pair(-y2, i)); plotX.emplace_back(make_pair(x2, -1), make_pair(-x1, -i)); plotY.emplace_back(make_pair(y2, -1), make_pair(-x2,-i)); } plotX.emplace_back(make_pair(0, 1), make_pair(-X, 0)); plotY.emplace_back(make_pair(0, 1), make_pair(-Y, 0)); plotX.emplace_back(make_pair(X, -1), make_pair(0, 0)); plotY.emplace_back(make_pair(Y, -1), make_pair(0, 0)); sort(plotX.begin(), plotX.end()); sort(plotY.begin(), plotY.end()); WYN = 0; for(int i = 0; i <= n; i++) pocz[i] = -1; for(int i = 0; i < plotX.size(); i++) { long long POS = plotX[i].first.first; long long otw = plotX[i].first.second; long long comp = plotX[i].second.first; long long para = abs(plotX[i].second.second); //printf("%lld %lld %lld %lld\n", POS, otw, comp, para); line[i] = POS; isBegin[i] = otw == 1; if(isBegin[i])pocz[para] = i; else kon[pocz[para]]=i; } //for(int i=0;i