| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 932117 |
2024-02-23T03:02:11 Z |
vjudge1 |
SIR (COI15_sir) |
C++17 |
|
127 ms |
28944 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 tinh(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) ;
}
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) ;
}
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});
}
// cout <<a.size() <<" 99999\n";
if(m == 1){
int l = 1, r = 2;
int sum = 0 , da=0;
while(tinh(ds[l].x , ds[l].y , ds[tren(r)].x , ds[(tren(r))].y , a[0].x , a[0].y) ){
tang(l , r , sum);
da = max(da , sum);
}
for(int i = 2 ; i <= n ; i ++){
giam(l , r , sum );
while(tinh(ds[l].x , ds[l].y , ds[tren(r)].x , ds[(tren(r))].y , a[0].x , a[0].y) ){
tang(l , r , sum);
da = max(da , sum);
}
}
cout <<da ;
return 0;
}
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]);
}
}
}
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 ;
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) ;
}
// cout <<x1 <<' '<< x2 <<" "<< y1 <<" "<<y2<<endl;
// if(tes(x1 , y1 , x2 , y2 , -3 , -4))
// cout << vt[2] <<" jhflkjhalkfjhalskjdfhalkjfhlsaudhsa;kldfihakl;hflkjhlfjkahalkjfgshkljasfh\n";
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);
}
}
A.push_back(A[1]);
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) ){
if(siz(l , r) >= 3){
da = max(da , sum);
}
if( !tes(x , y , u , v , ds[r].x , ds[r].y) || tes(x , y , u , v , ds[tren(r)].x , ds[tren(r)].y))
tang(l , r , sum);
else break;
}
giam(l , r , sum);
}
while(!tes(x , y , u , v , ds[r].x , ds[r].y) || 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:192:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<op>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for(int i = 1 ; i < A.size()-1 ; i ++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7364 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7516 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
3 ms |
7536 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
17008 KB |
Output is correct |
| 2 |
Correct |
122 ms |
15804 KB |
Output is correct |
| 3 |
Correct |
105 ms |
17188 KB |
Output is correct |
| 4 |
Correct |
27 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
96 ms |
15036 KB |
Output is correct |
| 6 |
Correct |
108 ms |
28944 KB |
Output is correct |
