首页 > 代码库 > Cubes-Codeforces-180E
Cubes-Codeforces-180E
Cubes:
我们先将每个正方形的光路投影找出来（在y轴上的截距所构成的区间）
然后，我们再考虑按照光线射到的先后顺序加入每个方格。
再用线段树统计这个投影区间内的最小高度的光线。这样我们就能够算出每个点被照亮的高度。
复杂度O(n2logn+).
注意：
在计算区间的时候选择前闭后开区间，这是因为我们要满足两个条件，
1.只通过一个点的光线不算照亮
2.假设先后修改（2,3），（1,2），（4,5）那么现在的（2,3）区间不能是(1,2)或(4,5)中间的一个.
代码很丑,凑合着看吧.(数据似乎没有和坐标轴平行的光,我就没管了.....)
1 #include<cstdlib> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 #include<map> 7 using namespace std; 8 const int maxn = 510, maxs = maxn * maxn * 5,inf = 0x3f3f3f3f; 9 const int dx[] = {0,0,0,1,1}, 10 dy[] = {0,0,1,0,1}; 11 int ct; 12 struct SEG{ 13 int sg[maxs * 3],tag[maxs * 3]; 14 void down(int x){ 15 if(tag[x]){ 16 sg[x << 1] = max(sg[x << 1], tag[x]); 17 sg[x << 1|1] = max(sg[x << 1|1], tag[x]); 18 tag[x << 1] = max(tag[x << 1], tag[x]); 19 tag[x <<1|1] = max(tag[x << 1|1], tag[x]); 20 tag[x] = 0; 21 } 22 } 23 int qer(int x,int l,int r,int nl,int nr){ 24 down(x); 25 if(l == nl && nr == r) return sg[x]; 26 int mid = (nl + nr) >> 1; 27 if(r <= mid) return qer(x << 1, l, r, nl, mid); 28 else if(l > mid) return qer(x << 1|1, l, r, mid + 1, nr); 29 else{ 30 int t1 = qer(x << 1, l, mid, nl, mid); 31 int t2 = qer(x << 1|1, mid + 1, r, mid+1, nr); 32 return min(t1,t2); 33 } 34 } 35 void mod(int x,int l,int r,int nl,int nr,int val){ 36 down(x); 37 if(l == nl && nr == r){ 38 sg[x] = max(sg[x],val), tag[x] = max(tag[x],val); 39 return; 40 } 41 int mid = (nl + nr) >> 1; 42 if(r <= mid){ 43 mod(x << 1, l, r, nl, mid, val); 44 } 45 else if(l > mid){ 46 mod(x << 1|1, l, r, mid + 1, nr, val); 47 } 48 else{ 49 mod(x << 1, l, mid, nl, mid, val); 50 mod(x << 1|1, mid + 1, r, mid + 1, nr, val); 51 } 52 sg[x] = min(sg[x << 1], sg[x << 1|1]); 53 } 54 55 }seg; 56 int n,vx,vy; 57 int tot; 58 struct grid{ 59 int x,y; 60 long long height; 61 }g[maxn * maxn + 100]; 62 int cmp(grid x, grid y){ 63 if(x.x != y.x) return x.x > y.x; 64 return x.y > y.y; 65 } 66 void trans(){ 67 if(vx > 0){ 68 vx = -vx; 69 for(int i = 1; i <= tot; ++i) g[i].x = n - g[i].x - 1; 70 } 71 if(vy > 0){ 72 vy = -vy; 73 for(int i = 1; i <= tot; ++i) g[i].y = n - g[i].y - 1; 74 } 75 if(vx == 0 && vy != 0){ 76 swap(vx,vy); 77 for(int i = 1; i <= tot; ++i){ 78 swap(g[i].x, g[i].y); 79 g[i].y = n - g[i].y - 1; 80 } 81 } 82 } 83 struct I{ 84 long long it; 85 int rank; 86 }data[maxn][maxn]; 87 map<long long, int>v; 88 map<long long, int>::iterator itr; 89 void inter(int x,int y){ 90 long long t = ((long double) y - vy * x / (long double)vx) * (long long)1e9; 91 data[x][y] = (I){t,0}; 92 v[t] = 0; 93 } 94 void calc(){ 95 for(int i = 0; i <= n; ++i) 96 for(int j = 0; j <= n; ++j) 97 inter(i,j); 98 for(itr = v.begin(); itr != v.end(); ++itr) 99 itr->second = ++ct;100 for(int i = 0; i <= n; ++i)101 for(int j = 0; j <= n; ++j){102 data[i][j].rank = v[data[i][j].it];103 }104 }105 long long ans;106 void ins(){107 sort(g + 1, g + tot + 1, cmp);108 for(int i = 1; i <= tot; ++i){109 int up = -inf, down = inf;110 for(int j = 1; j <= 4; ++j){111 int tx = g[i].x + dx[j], ty = g[i].y + dy[j];112 up = max(up, data[tx][ty].rank);113 down = min(down, data[tx][ty].rank);114 }115 int r = up - 1, l = down;116 if(l <= r && up >= 0){117 int t = seg.qer(1, l , r, 1, ct);118 ans += max(g[i].height - t, 0LL);119 seg.mod(1, l, r, 1, ct, g[i].height);120 }121 }122 }123 void spj(){124 long long ans = 0;125 sort(g + 1, g + tot + 1, cmp);126 for(int i = 1; i <= tot; ++i){127 int x = g[i].x, y = g[i].y;128 data[x][y].it = max(data[x][y].it, data[x+1][y].it);129 ans += max(g[i].height - data[x][y].it, 0LL);130 data[x][y].it = max(data[x][y].it, g[i].height);131 }132 cout << ans;133 }134 int main()135 {136 freopen("cubes.in","r",stdin);137 freopen("cubes.out","w",stdout);138 ios::sync_with_stdio(false);139 cin >> n >> vx >> vy;140 for(int i = 1; i <= n; ++i)141 for(int j = 1; j <= n; ++j){142 int t; cin >> t;143 g[++tot] = (grid){i-1,j-1,t};144 }145 trans();146 calc();147 ins();148 cout << ans;149 return 0;150 }
Cubes-Codeforces-180E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。