| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 487420 |
2021-11-15T13:04:51 Z |
Dirii |
SIR (COI15_sir) |
C++14 |
|
143 ms |
20764 KB |
// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "f"
using namespace std;
template <typename T> inline void Read(T &x){
x = 0; char c;
ll dau = 1;
while(!isdigit(c = getchar())) if(c == '-') dau = -1;
do{
x = x * 10 + c - '0';
} while (isdigit(c = getchar()));
x *= dau;
}
ll read(){
ll tmp;
cin >> tmp;
return tmp;
}
void giuncute(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
void OF(){
if(fopen(Fname".inp", "r")){
freopen(Fname".inp", "r", stdin);
freopen(Fname".out", "w", stdout);
} else if(fopen(Fname".in", "r")){
freopen(Fname".in", "r", stdin);
freopen(Fname".out", "w", stdout);
}
}
#define point pp(ll, ll)
cll mxn = 3e5 + 4;
ll n, m, ans = 0, cnt[mxn] = {0};
vec(point) cake, pep, conpep;
inline ll valccw(point &a, point &b, point &c){
return (b.first - a.first) * (c.second - b.second) - (b.second - a.second) * (c.first - b.first);
}
inline int ccw(point &a, point &b, point &c){
ll val = valccw(a, b, c);
return (val < 0 ? -1 : (val > 0));
}
void find_con(){
sort(pep.begin(), pep.end());
vec(point) up, down;
up.push_back(pep[0]);
down.push_back(pep[0]);
lp(i, 1, pep.size() - 1){
if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) <= 0){
while(up.size() > 1 && ccw(up[up.size() - 2], up.back(), pep[i]) > -1){
up.pop_back();
}
up.push_back(pep[i]);
}
if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) >= 0){
while(down.size() > 1 && ccw(down[down.size() - 2], down.back(), pep[i]) < 1){
down.pop_back();
}
down.push_back(pep[i]);
}
}
lp(i, 0, down.size() - 1) conpep.push_back(down[i]);
lpd(i, up.size() - 2, 1) conpep.push_back(up[i]);
}
int main(){
giuncute();
#ifndef ONLINE_JUDGE
OF();
#endif
cin >> n;
lp(i, 1, n){
point tmp;
cin >> tmp.first >> tmp.second;
cake.push_back(tmp);
}
cin >> m;
lp(i, 1, m){
point tmp;
cin >> tmp.first >> tmp.second;
pep.push_back(tmp);
}
find_con();
// for(auto i : conpep) cerr << i.first << ' ' << i.second << '\n';
ll i = 0, j = 0, s = 0;
while(ccw(conpep.back(), cake[i], conpep[0]) == 1 && conpep.size() > 1) ((--i) += n) %= n;
while(ccw(conpep.back(), cake[i], conpep[0]) != 1 && conpep.size() > 1) (++i) %= n;
j = (i + 1) % n;
// while(ccw(conpep[0], cake[(j + 1) % n], conpep[1]) == 1){
// s += valccw(cake[(j + 1) % n], cake[i], cake[j]);
// (++j) %= n;
// }
ans = 0;
lp(cur, 0, conpep.size() - 1){
ll ncur = (cur + 1) % conpep.size();
// while(ccw(conpep[cur], cake[j], conpep[ncur]) != 1){
// s += valccw(cake[(j + 1) % n], cake[i], cake[j]);
// (++j) %= n;
// }
// while(ccw(conpep[cur], cake[(j + 1) % n], conpep[ncur]) == 1){
// s += valccw(cake[(j + 1) % n], cake[i], cake[j]);
// (++j) %= n;
// }
// while(ccw(conpep[cur], cake[i], conpep[ncur]) != 1){
// s -= valccw(cake[i], cake[(i + 1) % n], cake[j]);
// (++i) %= n;
// }
while(ccw(cake[i], conpep[cur], conpep[ncur]) == 1 || conpep.size() == 1){
bool ok = 1;
while(ccw(cake[(j + 1) % n], conpep[cur], cake[i]) == 1){
s += valccw(cake[(j + 1) % n], cake[i], cake[j]);
(++j) %= n;
}
ans = max(ans, s);
s -= valccw(cake[i], cake[(i + 1) % n], cake[j]);
(++i) %= n;
if(i == j) (++j) %= n;
if(cnt[i]) break;
cnt[i] = 1;
}
ans = max(ans, s);
}
cout << ans;
}
Compilation message
sir.cpp: In function 'void find_con()':
sir.cpp:7:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define lp(a, b, c) for(ll a = b; a <= c; ++a)
......
66 | lp(i, 1, pep.size() - 1){
| ~~~~~~~~~~~~~~~~~~~~
sir.cpp:66:5: note: in expansion of macro 'lp'
66 | lp(i, 1, pep.size() - 1){
| ^~
sir.cpp:67:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) <= 0){
| ~~^~~~~~~~~~~~~~~~~
sir.cpp:73:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) >= 0){
| ~~^~~~~~~~~~~~~~~~~
sir.cpp:7:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define lp(a, b, c) for(ll a = b; a <= c; ++a)
......
80 | lp(i, 0, down.size() - 1) conpep.push_back(down[i]);
| ~~~~~~~~~~~~~~~~~~~~~
sir.cpp:80:5: note: in expansion of macro 'lp'
80 | lp(i, 0, down.size() - 1) conpep.push_back(down[i]);
| ^~
sir.cpp: In function 'int main()':
sir.cpp:7:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define lp(a, b, c) for(ll a = b; a <= c; ++a)
......
112 | lp(cur, 0, conpep.size() - 1){
| ~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:112:5: note: in expansion of macro 'lp'
112 | lp(cur, 0, conpep.size() - 1){
| ^~
sir.cpp:127:18: warning: unused variable 'ok' [-Wunused-variable]
127 | bool ok = 1;
| ^~
sir.cpp: In function 'void OF()':
sir.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen(Fname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen(Fname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen(Fname".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen(Fname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
2 ms |
592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
143 ms |
15172 KB |
Output is correct |
| 2 |
Correct |
139 ms |
11956 KB |
Output is correct |
| 3 |
Correct |
113 ms |
15664 KB |
Output is correct |
| 4 |
Correct |
35 ms |
4476 KB |
Output is correct |
| 5 |
Correct |
112 ms |
20764 KB |
Output is correct |
| 6 |
Correct |
116 ms |
17976 KB |
Output is correct |
