| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 859543 |
2023-10-10T10:00:02 Z |
mychecksedad |
SIR (COI15_sir) |
C++17 |
|
136 ms |
35532 KB |
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22;
struct P{
ll x, y;
void read(){
cin >> x >> y;
}
ll operator * (const P &other) const{
return x * other.y - y * other.x;
}
P operator - (const P &other) const{
return P{x - other.x, y - other.y};
}
bool operator < (const P &other) const{
return (x == other.x ? y < other.y : x < other.x);
};
};
int point_loc(P a, P b, P c){ // where is point c according to (a,b)
b = b - a;
c = c - a;
if(b * c > 0) return 0; // upper
if(b * c < 0) return 2; // under
return 1; // on
}
struct Polygon{
vector<P> poly;
Polygon(int n){
poly.resize(n);
for(auto &p: poly) p.read();
}
void ConvexHull(){
sort(all(poly));
vector<P> ch;
for(int i = 0; i < poly.size(); ++i){
while(ch.size() > 1 && point_loc(ch[ch.size() - 2], ch[ch.size() - 1], poly[i]) == 0){
ch.pop_back();
}
ch.pb(poly[i]);
}
reverse(all(poly));
// for(auto p: ch){
// cout << p.x << ' ' << p.y << '\n';
// }
// en;
ch.pop_back();
for(int i = 0; i < poly.size(); ++i){
while(ch.size() > 1 && point_loc(ch[ch.size() - 2], ch[ch.size() - 1], poly[i]) == 0){
ch.pop_back();
}
ch.pb(poly[i]);
}
ch.pop_back();
poly = ch;
}
};
int n, m;
void solve(){
cin >> n;
Polygon cheese(n);
cin >> m;
Polygon pepper(m);
cheese.ConvexHull();
pepper.ConvexHull();
ll ans = 0;
vector<int> tang(cheese.poly.size());
m = pepper.poly.size();
n = cheese.poly.size();
// en;
// for(auto p: cheese.poly){
// cout <<p.x << ' ' << p.y << '\n';
// }
// en;
// for(auto p: pepper.poly){
// cout <<p.x << ' ' << p.y << '\n';
// }
// en;
if(m > 1){
for(int i = 0; i < m; ++i){
if(point_loc(cheese.poly[0], pepper.poly[i], pepper.poly[(i + 1) % m]) == 2){
tang[0] = i;
break;
}
}
// cout << "g " << endl;
for(int i = 1; i < n; ++i){
tang[i] = tang[i - 1];
while(point_loc(cheese.poly[i], pepper.poly[tang[i] % m], pepper.poly[(tang[i] + 1) % m]) == 0){
tang[i]++;
tang[i] %= m;
}
}
}else{
for(int i = 0; i < n; ++i) tang[i] = 0;
}
ll cur = 0;
int cp = 1;
for(int i = 0; i < n; ++i){
while(point_loc(cheese.poly[i], pepper.poly[tang[i]], cheese.poly[(cp + 1) % n]) == 0){
cur += abs((cheese.poly[cp % n] - cheese.poly[i]) * (cheese.poly[(cp + 1) % n] - cheese.poly[i]));
++cp;
}
ans = max(ans, cur);
cur -= abs((cheese.poly[(i + 1) % n] - cheese.poly[i]) * (cheese.poly[cp % n] - cheese.poly[(i + 1) % n]));
// cout << cur << ' ' << cp << endl;
}
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
sir.cpp: In member function 'void Polygon::ConvexHull()':
sir.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<P>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0; i < poly.size(); ++i){
| ~~^~~~~~~~~~~~~
sir.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<P>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0; i < poly.size(); ++i){
| ~~^~~~~~~~~~~~~
sir.cpp: In function 'int main()':
sir.cpp:128:15: warning: unused variable 'aa' [-Wunused-variable]
128 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
13000 KB |
Output is correct |
| 2 |
Correct |
136 ms |
22996 KB |
Output is correct |
| 3 |
Correct |
111 ms |
21756 KB |
Output is correct |
| 4 |
Correct |
38 ms |
11720 KB |
Output is correct |
| 5 |
Correct |
99 ms |
17592 KB |
Output is correct |
| 6 |
Correct |
131 ms |
35532 KB |
Output is correct |
