oj.uz

답안 #44449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44449 2018-04-02T07:46:58 Z Yehezkiel Svjetlost (COI18_svjetlost) C++11
12 / 100
 170 ms 132860 KB 
#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+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){
	return vec(p2.x-p1.x,p2.y-p1.y);
}
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());
	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:151: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:231:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
svjetlost.cpp:233: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:234:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
svjetlost.cpp:238:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&querylist[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 65916 KB 11 numbers
2 Correct 60 ms 66020 KB 41 numbers
3 Correct 58 ms 66200 KB 11 numbers
4 Correct 66 ms 66200 KB 93 numbers

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 65916 KB 11 numbers
2 Correct 60 ms 66020 KB 41 numbers
3 Correct 58 ms 66200 KB 11 numbers
4 Correct 66 ms 66200 KB 93 numbers
5 Correct 61 ms 66432 KB 101 numbers
6 Runtime error 132 ms 132668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 132668 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Runtime error 166 ms 132668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 170 ms 132860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 65916 KB 11 numbers
2 Correct 60 ms 66020 KB 41 numbers
3 Correct 58 ms 66200 KB 11 numbers
4 Correct 66 ms 66200 KB 93 numbers
5 Correct 61 ms 66432 KB 101 numbers
6 Runtime error 132 ms 132668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -