| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 932096 |
2024-02-23T01:31:49 Z |
vjudge1 |
SIR (COI15_sir) |
C++17 |
|
131 ms |
26036 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct op{
int x ,y;
};
bool po(op a , op b){
return (a.x< b.x) || (a.x==b.x && a.y< b.y) ;
}
int n ;
vector <op> a ,A , ds(3e5+10);
bool kt(int i){
int k = A.size()-1;
int m = A[k].x - A[k-1].x;
int n = A[k].y - A[k-1].y ;
int u = a[i].x - A[k-1].x;
int v = a[i].y - A[k-1].y ;
return (m*v - n*u >= 0);
}
bool tes(int& x1 , int& y1 ,int& x2 ,int& y2 ,int& u1 ,int& v1){
int x = x2-x1;
int y = y2-y1;
int u = u1 - x1 ;
int v = v1 - y1 ;
return (x*v - y*u < 0) ? 1 : 0;
}
bool tet(int x1 , int y1 , int x2 , int y2 , int u1 , int v1) {
int x = x2-x1;
int y = y2-y1;
int u = u1 - x1 ;
int v = v1 - y1 ;
return (x*v - y*u > 0);
}
int tren(int i ){
if(i<n ) return i+1;
return 1;
}
int siz(int l , int r){
return (l<= r) ? r-l+1 : r + n-l+1;
}
void tang(int& l , int& r, int& sum ){
int moi = tren(r);
int big = siz(l , r);
if(big != 1){
sum -= ds[r].x*ds[l].y - ds[l].x*ds[r].y;
}
sum += ds[r].x*ds[moi].y - ds[moi].x*ds[r].y;
sum += ds[moi].x*ds[l].y - ds[l].x*ds[moi].y;
r = moi;
}
void giam(int& l , int& r , int& sum){
int moi = tren(l);
int big = siz(l , r);
if(big == 2){
sum = 0;
l = moi;
return;
}
sum -= ds[r].x*ds[l].y - ds[l].x*ds[r].y;
sum -= ds[l].x*ds[moi].y - ds[moi].x*ds[l].y;
sum += ds[r].x*ds[moi].y - ds[moi].x*ds[r].y;
l = moi;
}
signed main(){
// freopen("DAGIAC.INP" , "r" , stdin);
// freopen("DAGIAC.OUT" , "w" , stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m , x , y;
cin >> n ;
for(int i = 1 ; i <= n ; i ++){
cin >> x >> y;
ds[i]= {x , y};
}
cin >> m ;
for(int i = 0 ; i < m ;i ++){
cin >> x >> y;
a.push_back({x , y});
}
sort(a.begin() , a.end() , po);
for(int i = 0 ; i < m ; i++){
if(A.size() <2) A.push_back(a[i]);
else {
if(kt(i)){
A.push_back(a[i]);
}else {
while(!kt(i)){
A.pop_back();
if(A.size() < 2) {
break;
}
}A.push_back(a[i]);
}
}
}int P = a.size();
for(int i =m -2 ; i >=0 ; i--){
if(A.size() <2) A.push_back(a[i]);
else {
if(kt(i))
A.push_back(a[i]);
else {
while(!kt(i)){
A.pop_back();
if(A.size() < 2) {
break;
}
}A.push_back(a[i]);
}
}
}
int l = 0 , r = 0 ;
// for(int i = 0 ; i < A.size()-1 ; i++) cout << A[i].x <<" " << A[i].y << '\n';
int x1 = a[0].x ;
int y1 = a[0].y;
int x2 = a[1].x;
int y2 = a[1].y;
vector<int> vt(3e5+5);
for(int i = 1 ; i <= n ; i ++){
vt[i] = tes(x1 , y1 , x2 , y2 , ds[i].x , ds[i].y) ;
}
vt[0] = vt[n];
vt[n+1] = vt[1];
for(int i = 1 ; i <= n ; i ++){
if(vt[i] == 1 && vt[i-1] ==0){
l = i;
}
if(vt[i] == 1 && vt[i+1] ==0){
r = i;
}
}
int sum = 0 , da= 0;
if(l <= r){
if(r-l +1 >= 2){
for(int i = l ; i < r ;i ++){
sum += ds[i].x*ds[i+1].y - ds[i+1].x*ds[i].y;
}
sum += ds[r].x*ds[l].y - ds[l].x*ds[r].y;
if(r-l+1 >= 3){
da = max(da , sum);
}
}
}else{
if(r + n-l +1 >= 2){
for(int i = 1 ; i < r ; i ++){
sum += ds[i].x*ds[i+1].y - ds[i+1].x*ds[i].y;
}
sum += ds[r].x*ds[l].y - ds[l].x*ds[r].y;
for(int i = l ; i < n ; i++){
sum += ds[i].x*ds[i+1].y - ds[i+1].x*ds[i].y;
}
sum += ds[n].x*ds[1].y - ds[1].x*ds[n].y;
if(r + n - l + 1 >= 3) da = max(da , sum);
}
}
// if(tet(-3 , 3 , 3 , -4 , 0 , -3)){
// cout <<9999999999 <<endl;
// }
// cout << l << " " << r<<" pppp\n";
for(int i = 1 ; i < A.size()-1 ; i ++){
int x = A[i].x;
int y = A[i].y;
int u = A[i+1].x;
int v = A[i+1].y;
while(!tes(x , y , u , v , ds[l].x , ds[l].y)){
while(tet(ds[l].x , ds[l].y , ds[r].x , ds[r].y , x , y) && tet(ds[l].x , ds[l].y , ds[r].x , ds[r].y , u , v)){
if(siz(l , r) >= 3){
da = max(da , sum);
// cout << l <<" "<< r <<" op\n" <<x<<" "<< y <<" :: "<< ds[l].x <<" "<<ds[l].y <<" "<<ds[r].x<<" "<<ds[r].y<<'\n';
// cout <<sum <<endl;
}
if(tes(x , y , u , v , ds[tren(r)].x , ds[tren(r)].y))
tang(l , r , sum);
else break;
}
// cout <<l <<" "<< r<<" cc\n";
giam(l , r , sum);
}
while(tes(x , y , u , v , ds[tren(r)].x , ds[tren(r)].y)){
tang(l , r , sum);
}
if(siz(l , r) >= 3){
da = max(da , sum);
// cout <<sum <<endl;
}
}
cout <<da;
}
Compilation message
sir.cpp: In function 'int main()':
sir.cpp:163:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<op>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i = 1 ; i < A.size()-1 ; i ++){
| ~~^~~~~~~~~~~~
sir.cpp:98:7: warning: unused variable 'P' [-Wunused-variable]
98 | }int P = a.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
26036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
