vijos1055 奶牛浴场

挺好的一道题呢

O(n^2)或者O(wh)

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream> using namespace std; void setIO(const string& s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
} template<typename Q> Q read(Q& x) {
static char c, f;
for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;
for(x = ; isdigit(c); c = getchar()) x = x * + c - '';
return f && (x = -x), x;
}
template<typename Q> Q read() {
static Q x; return read(x);
} const int N = + ; struct Node {
int x, y;
Node(int x = , int y = ) : x(x), y(y) {}
}p[N]; bool cmpx(const Node& lhs, const Node& rhs) {
return lhs.x < rhs.x;
} bool cmpy(const Node& lhs, const Node& rhs) {
return lhs.y < rhs.y;
} int L, H, n;
int calc() {
int ans = ;
for(int i = ; i < n; i++) {
int U = H, D = ;
for(int j = i + ; j < n; j++) {
ans = max(ans, (p[j].x - p[i].x) * (U - D));
if(D <= p[j].y && p[j].y <= U) {
if(p[j].y > p[i].y) U = p[j].y;
else D = p[j].y;
}
if(U == D) break;
}
}
return ans;
} int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif read(H), read(L), read(n);
for(int i = ; i < n; i++) {
int x = read<int>(), y = read<int>();
p[i] = Node(x, y);
}
p[n++] = Node(, );
p[n++] = Node(, H);
p[n++] = Node(L, );
p[n++] = Node(L, H); int ans = ;
sort(p, p + n, cmpy);
for(int i = ; i < n; i++) {
ans = max(ans, (p[i].y - p[i-].y) * L);
}
sort(p, p + n, cmpx);
ans = max(ans, calc());
for(int i = ; i < n; i++) p[i].x *= -;
reverse(p, p + n);
printf("%d\n", max(ans, calc())); return ;
}
上一篇:简单说一个IOCP不好的地方


下一篇:iocp还是select