#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;
const int MAXN=100000;
const int treesize=1048576;
const LD EPS=(LD) 0.000000001;
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 sqrt(x*x+y*y);
}
};
struct segtree{
LD lazy,maks;
segtree(){
lazy=maks=0;
}
void update(LD tambah)
{
maks+=tambah;
lazy+=tambah;
}
};
int n,q,ulang;
set <int> daftar;
vector <int> querylist;
vector <LD> press,ans;
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){
return vec(p2.x-p1.x,p2.y-p1.y);
}
LD jarak(point p1,point p2){
return ToVec(p1,p2).val();
}
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;
update(0,(int) press.size()*3-1,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(){
for(int i=0;i<5;i++)
press.pb((LD) 90.0*i);
sort(all(press));
vector <LD> baru;
baru.pb(press[0]);
for(int i=1;i<press.size();i++)
{
if(!(fabs(baru.back()-press[i])<EPS))
baru.pb(press[i]);
}
press=baru;
}
int nilaipress(LD a){
int bawah=0,atas=press.size()-1,mid;
while(bawah<=atas)
{
mid=(bawah+atas)>>1;
if(press[mid]<a-EPS)
bawah=mid+1;
else
atas=mid-1;
}
return bawah*3+1;
}
void upd(LD sudutL,LD sudutR,LD val){
if(ulang==0)
{
press.pb(sudutL);
press.pb(sudutR);
return;
}
cout<<"updatenya "<<sudutL<<" "<<sudutR<<" sebanyak "<<val<<endl;
if(sudutR>360.0+EPS)
{
cout<<"pecah "<<endl;
update(nilaipress(sudutL)+1,nilaipress(360.0),val);
update(nilaipress(0.0),nilaipress(sudutR-360.0)-1,val);
}
else
{
update(nilaipress(sudutL)+1,nilaipress(sudutR)-1,val);
}
}
void remove(int tadi,int now){
LD tetha=sudut(ToVec(plist[now],plist[tadi]));
upd(tetha,tetha+180.0,-jarak(plist[now],plist[tadi]));
}
void add(int tadi,int now){
//cout<<"add "<<tadi<<" "<<now<<endl;
LD tetha=sudut(ToVec(plist[now],plist[tadi]));
upd(tetha,tetha+180.0,jarak(plist[now],plist[tadi]));
}
void enyahkan(int pos){
if(ulang)
cout<<"menghapus "<<pos+1<<endl;
auto it=daftar.find(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:118: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:192:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
svjetlost.cpp:194: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:195:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
svjetlost.cpp:199: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 |
62 ms |
66040 KB |
41 numbers |
| 3 |
Correct |
59 ms |
66100 KB |
11 numbers |
| 4 |
Correct |
60 ms |
66340 KB |
93 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
66040 KB |
11 numbers |
| 2 |
Correct |
62 ms |
66040 KB |
41 numbers |
| 3 |
Correct |
59 ms |
66100 KB |
11 numbers |
| 4 |
Correct |
60 ms |
66340 KB |
93 numbers |
| 5 |
Incorrect |
66 ms |
66440 KB |
93rd numbers differ - expected: '3170556.4232043056', found: '3156917.4538862808', error = '0.0043017589' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
66440 KB |
found '32934.3604541195', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Incorrect |
88 ms |
66568 KB |
1st numbers differ - expected: '31571636.3365447633', found: '0.0000000000', error = '1.0000000000' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
67056 KB |
1st numbers differ - expected: '1042655967.3918291330', found: '0.0000000000', error = '1.0000000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
66040 KB |
11 numbers |
| 2 |
Correct |
62 ms |
66040 KB |
41 numbers |
| 3 |
Correct |
59 ms |
66100 KB |
11 numbers |
| 4 |
Correct |
60 ms |
66340 KB |
93 numbers |
| 5 |
Incorrect |
66 ms |
66440 KB |
93rd numbers differ - expected: '3170556.4232043056', found: '3156917.4538862808', error = '0.0043017589' |
| 6 |
Halted |
0 ms |
0 KB |
- |
