Saratov State University :: Online Contester


::Go
- home
- news
- register
- update personal info
- problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- links
- projects

::Poll
Are you registered on Codeforces?
Yes
No
What is it???

[results]

::webboard

WA#1. don't know why
Author: ysymyth
ID: 052439
Problem: 277
Contest: 0
Date: 2013-03-02 20:21:39

help please!

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define de(it) tmp=*it; tmp.Print()
using namespace std;
typedef long long ll;

struct pnt{
ll x,y,d;
double z; //tan theta
void Build(pnt o){z=atan2(y-o.y,x-o.x); d=(y-o.y)*(y-o.y)+(x-o.x)*(x-o.x);}
void Read(){
scanf("%lld %lld",&x,&y);
x*=3LL, y*=3LL;
}
void Print(){printf("%lld %lldn",x,y);}
void operator +=(const pnt&o){ x+=o.x, y+=o.y;}
bool operator < (const pnt&o) const {return z+1e-10<o.z || fabs(z-o.z)<1e-10 && d<o.d;}

}a[5],s,p;
int n; long long ans=0;

ll crs(pnt a,pnt b,pnt c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}

set<pnt> Set;
typedef set<pnt>::iterator IT;

IT Left(IT it){return it==Set.begin()? --Set.end() : --it;}
IT Right(IT it){return it==--Set.end()? Set.begin(): ++it;}

int main(){
rep(i,3) a[i].Read(),s+=a[i+1]; s.x/=3, s.y/=3;
if (crs(s,a[0],a[1])<0) swap(a[0],a[2]); ans=crs(a[0],a[1],a[2]);
rep(i,3) a[i].Build(s); Set.insert(a,a+3);

IT l,r,it,ll,rr; pnt tmp;
cin>>n;
rep(t,n){
p.Read(); p.Build(s);
r=Set.lower_bound(p); if(r==Set.end()) r=Set.begin();
l=Left(r);
if(crs(*l,p,*r)<=0){
printf("%lldn",ans/9);
continue;
}

Set.insert(p); it=Set.find(p);
l=Left(it),r=Right(it); ans+=crs(*l,*it,*r);

l=Left(it), ll=Left(l);
while(crs(*ll,*l,*it)<0){
ans-=crs(*ll,*l,*it);
Set.erase(l);
l=ll; ll=Left(l);
}

r=Right(it), rr=Right(r);
while(crs(*it,*r,*rr)<0){
ans-=crs(*it,*r,*rr);
Set.erase(r);
r=rr; rr=Right(r);
}
printf("%lldn",ans/9);
}
}


see sub-tree reply to that message


::Login
Forgot password?

::News
22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553).
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).

::Counter

Server time: 2017-11-22 04:42:52Online Contester Team © 2002 - 2016. All rights reserved.