#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
//#include <cassert>
#include <algorithm>
#include <iomanip>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define cout if(false)cout
typedef long double LD;
typedef long long LL;
//typedef __int128 LL;
const int MAXN=100000;
const int treesize=1048576;
const LD EPS=(LD) 0.00000000001;
struct point{
int x,y;
point(int _x,int _y){
x=_x;
y=_y;
}
point(){
}
};
struct vec{
int x,y;
vec(int _x,int _y){
x=_x;
y=_y;
}
vec(){
}
LD val(){
return (LD) sqrt( (LL) x*x+(LL) y*y);
}
};
struct segtree{
LD lazy,maks;
segtree(){
lazy=maks=0;
}
void update(LD tambah)
{
maks+=tambah;
lazy+=tambah;
}
};
int n,q,ulang,event;
set <int> daftar;
vector <int> querylist;
vector <LD> ans;
vector <vec> press;
point plist[MAXN+5];
LD Drajat(LD Radian){
return Radian*180.0/acos(-1.0);
}
LD Radian(LD Drajat){
return Drajat*acos(-1.0)/180.0;
}
/*LD sudut(vec v){
LD ret=atan2(v.y,v.x);
ret=Drajat(ret);
if(ret<-EPS)
ret+=360.0;
return ret;
}*/
vec ToVec(point p1,point p2){
vec ret;
ret.x=p2.x-p1.x;
ret.y=p2.y-p1.y;
//assert(ret.val()>EPS);
return ret;
}
LD jarak(point p1,point p2){
return ToVec(p1,p2).val();
}
int sign(LL angka){
if(angka>0)
return 1;
if(angka<0)
return -1;
return 0;
}
LL cross(vec v1,vec v2){
return (LL) v1.x*v2.y - (LL) v1.y*v2.x;
}
bool cmp(vec v1, vec v2){
//assert(v1.val()>EPS&&v2.val()>EPS);
if(sign(v1.y)==sign(v2.y)) //case ++ dan -- dan 00
{
if(sign(v1.y)) //case ++ dan --
return sign(cross(v1,v2))==1;
else //case 00
return sign(v1.x)>sign(v2.x);
}
if((sign(v1.y)==1&&sign(v2.y)==0)||(sign(v1.y)==0&&sign(v2.y)==1)) //case +0 dan 0+
{
if(sign(v1.y)==0)
return (sign(v1.x)==1); //kalau positif berarti lebih kecil else lebih besar
else
return !(sign(v2.x)==1);
}
else //casae +- , -+ , 0- ,-0
{
return sign(v1.y)>sign(v2.y);
}
}
segtree tree[(treesize<<1)+5];
void pushdown(int indeks){
tree[indeks<<1].update(tree[indeks].lazy);
tree[(indeks<<1)|1].update(tree[indeks].lazy);
tree[indeks].lazy=0;
}
void pullup(int indeks){
//assert(fabs(tree[indeks].lazy)<EPS);
tree[indeks].maks=max(tree[indeks<<1].maks,tree[(indeks<<1)|1].maks);
}
void update(int kiri,int kanan,int indeks,int l,int r,LD tambah){
if(l<=kiri&&kanan<=r)
{
tree[indeks].update(tambah);
return;
}
if(l>kanan||r<kiri)
return;
int mid=(kiri+kanan)>>1;
pushdown(indeks);
update(kiri,mid,indeks<<1,l,r,tambah);
update(mid+1,kanan,(indeks<<1)|1,l,r,tambah);
pullup(indeks);
}
void update(int l,int r,LD tambah){
//cout<<"updating pada tree "<<l<<" "<<r<<" sebanyak "<<tambah<<endl<<endl;
//assert(l<=r);
update(0,event,1,l,r,tambah);
}
LD dabest(){
//cout<<"test"<<endl;
//cout<<"this is dabest "<<tree[1].maks<<endl;
//cout<<"dabest "<<tree[1].maks<<endl<<endl<<endl;
return tree[1].maks;
}
void compress(){
sort(all(press),cmp);
vector <vec> baru;
baru.pb(press[0]);
for(int i=1;i<press.size();i++)
{
if(cmp(baru.back(),press[i]))
baru.pb(press[i]);
}
press=baru;
event=3*press.size()-1;
}
int nilaipress(vec v){
//assert(v.val()>EPS);
int bawah=0,atas=press.size()-1,mid;
while(bawah<=atas)
{
mid=(bawah+atas)>>1;
if(cmp(press[mid],v))
bawah=mid+1;
else
atas=mid-1;
}
return bawah*3+1;
}
void upd(vec vL,vec vR,LD val){
if(ulang==0)
{
press.pb(vL);
press.pb(vR);
return;
}
int l=nilaipress(vL);
int r=nilaipress(vR);
if(r<l)
{
cout<<"pecah "<<endl;
update(l+1,event,val);
update(0,r-1,val);
}
else
{
update(l+1,r-1,val);
}
}
void remove(int tadi,int now){
//assert(tadi!=now);
vec v1=ToVec(plist[now],plist[tadi]);
vec v2=ToVec(plist[tadi],plist[now]);
upd(v1,v2,-jarak(plist[now],plist[tadi]));
}
void add(int tadi,int now){
//assert(tadi!=now);
//cout<<"add "<<tadi<<" "<<now<<endl;
vec v1=ToVec(plist[now],plist[tadi]);
vec v2=ToVec(plist[tadi],plist[now]);
upd(v1,v2,jarak(plist[now],plist[tadi]));
}
void enyahkan(int pos){
auto it=daftar.find(pos);
//assert(it!=daftar.end());
//assert(*it==pos);
int a,b,c;
b=pos;
if(it==daftar.begin())
a=*prev(daftar.end());
else
a=*prev(it);
if(next(it)==daftar.end())
c=*daftar.begin();
else
c=*next(it);
remove(a,b);
remove(b,c);
add(a,c);
daftar.erase(it);
}
void BacaInput(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&plist[i].x,&plist[i].y);
scanf("%d",&q);
querylist.resize(q);
for(int i=0;i<q;i++)
{
scanf("%d",&querylist[i]);
querylist[i]--;
}
}
void Solve(){
for(ulang=0;ulang<2;ulang++)
{
//cout<<"pengulangan ke "<<ulang<<endl;
daftar.clear();
for(int i=0;i<n;i++)
{
daftar.insert(i);
if(i)
add(i-1,i);
else
add(n-1,i);
}
if(ulang) //mau dijawab
ans.pb(dabest());
for(auto isi:querylist)
{
enyahkan(isi);
if(ulang) //mau dijawab
ans.pb(dabest());
}
if(ulang==0)
compress();
}
}
void PrintAll(){
for(auto isi:ans)
{
printf("%.10Lf\n",isi);
}
}
int main()
{
//cout<<"membaca input"<<endl;
BacaInput();
//cout<<"solving"<<endl;
Solve();
//cout<<"printing solution"<<endl;
PrintAll();
}
Compilation message
svjetlost.cpp: In function 'void compress()':
svjetlost.cpp:155:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<press.size();i++)
~^~~~~~~~~~~~~
svjetlost.cpp: In function 'void BacaInput()':
svjetlost.cpp:236:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
svjetlost.cpp:238:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&plist[i].x,&plist[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:239:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
svjetlost.cpp:243:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&querylist[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
66040 KB |
11 numbers |
| 2 |
Correct |
59 ms |
66152 KB |
41 numbers |
| 3 |
Correct |
60 ms |
66152 KB |
11 numbers |
| 4 |
Correct |
80 ms |
66152 KB |
93 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
66040 KB |
11 numbers |
| 2 |
Correct |
59 ms |
66152 KB |
41 numbers |
| 3 |
Correct |
60 ms |
66152 KB |
11 numbers |
| 4 |
Correct |
80 ms |
66152 KB |
93 numbers |
| 5 |
Correct |
61 ms |
66152 KB |
101 numbers |
| 6 |
Correct |
71 ms |
66396 KB |
1201 numbers |
| 7 |
Correct |
76 ms |
66524 KB |
1556 numbers |
| 8 |
Correct |
80 ms |
66524 KB |
1996 numbers |
| 9 |
Correct |
79 ms |
66560 KB |
1960 numbers |
| 10 |
Correct |
78 ms |
66592 KB |
1991 numbers |
| 11 |
Correct |
79 ms |
66592 KB |
1963 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
66592 KB |
found '32934.3604541195', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Correct |
62 ms |
66592 KB |
found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000' |
| 3 |
Correct |
95 ms |
67460 KB |
found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000' |
| 4 |
Correct |
123 ms |
68476 KB |
found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000' |
| 5 |
Correct |
384 ms |
75376 KB |
found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000' |
| 6 |
Correct |
385 ms |
75508 KB |
found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
75508 KB |
1001 numbers |
| 2 |
Correct |
290 ms |
75508 KB |
15001 numbers |
| 3 |
Correct |
671 ms |
75644 KB |
44445 numbers |
| 4 |
Correct |
623 ms |
76792 KB |
22223 numbers |
| 5 |
Runtime error |
364 ms |
154748 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
66040 KB |
11 numbers |
| 2 |
Correct |
59 ms |
66152 KB |
41 numbers |
| 3 |
Correct |
60 ms |
66152 KB |
11 numbers |
| 4 |
Correct |
80 ms |
66152 KB |
93 numbers |
| 5 |
Correct |
61 ms |
66152 KB |
101 numbers |
| 6 |
Correct |
71 ms |
66396 KB |
1201 numbers |
| 7 |
Correct |
76 ms |
66524 KB |
1556 numbers |
| 8 |
Correct |
80 ms |
66524 KB |
1996 numbers |
| 9 |
Correct |
79 ms |
66560 KB |
1960 numbers |
| 10 |
Correct |
78 ms |
66592 KB |
1991 numbers |
| 11 |
Correct |
79 ms |
66592 KB |
1963 numbers |
| 12 |
Correct |
71 ms |
66592 KB |
found '32934.3604541195', expected '32934.3604541195', error '0.0000000000' |
| 13 |
Correct |
62 ms |
66592 KB |
found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000' |
| 14 |
Correct |
95 ms |
67460 KB |
found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000' |
| 15 |
Correct |
123 ms |
68476 KB |
found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000' |
| 16 |
Correct |
384 ms |
75376 KB |
found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000' |
| 17 |
Correct |
385 ms |
75508 KB |
found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000' |
| 18 |
Correct |
76 ms |
75508 KB |
1001 numbers |
| 19 |
Correct |
290 ms |
75508 KB |
15001 numbers |
| 20 |
Correct |
671 ms |
75644 KB |
44445 numbers |
| 21 |
Correct |
623 ms |
76792 KB |
22223 numbers |
| 22 |
Runtime error |
364 ms |
154748 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
