Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 0ms过 纪念一下(写了4个小时调错无数的菜菜)

Posted by 980306 at 2017-05-30 15:54:43 on Problem 1151
```#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<stdlib.h>
#include<cstdio>
#include<string>
#include<map>
#include<string.h>
#include<set>
using namespace std;

typedef long long ll;
typedef  pair<int,int> P;
const int INF = 0x7fffffff;
const int MAX_N = 10000;
const int MAX_V = 0;
const int MAX_M = 0;

//Define array zone
int N, T;
double x[4*MAX_N], ty[4*MAX_N], ty1[4*MAX_N], val[4*MAX_N];
int data[4*MAX_N];
map<double, int> m;

//Cut-off rule
struct edge{
int tcor, bcor;
edge(){}
edge(int tcor, int bcor):tcor(tcor), bcor(bcor){}
}y[4*MAX_N];

//establish segment tree

void init(int k, int l, int r){
data[k] = 0;
//leaf node
if(r-l==1){
val[k] = ty[l+1]-ty[l];
}
else{
int chl = 2*k+1, chr = 2*k+2;
init(chl, l, (l+r)/2);
init(chr, (l+r)/2, r);
val[k] = val[chl] + val[chr];
}
}

//add edge to section a, b,      k is the index of the node,
void add(int a, int b, int x, int k, int l, int r){
if(a<=l&&r<=b) data[k] += x;
else if(l<b&&a<r){
add(a, b, x, k*2+1, l, (l+r)/2);
add(a, b, x, k*2+2, (l+r)/2, r);
}
}

double sum(int a, int b, int k, int l, int r){
if(b<=l||a>=r) return 0;
if(a<=l && r<= b){
if(data[k]>0) return val[k];
if(data[k]==0&&r-l==1) return 0;
else return sum(a,b,2*k+1, l, (l+r)/2)
+sum(a,b,2*k+2,(l+r)/2, r);
}
else{
return sum(a,b,2*k+1, l, (l+r)/2)
+sum(a,b,2*k+2,(l+r)/2, r);
}
}

void solve(){
vector<pair<double, int> > events;
for(int i=0; i<2*N; i++){
events.push_back(make_pair(x[i],i));
}
sort(events.begin(), events.begin()+2*N);

//discretize
sort(ty, ty+2*N);
int num = unique(ty,ty+2*N)-ty;
for(int i=0; i<num; i++)
m[ty[i]] = i;

//establish edges
for(int i=0; i<N; i++){
y[i] = edge( m[max(ty1[i],ty1[i+N])], m[min(ty1[i],ty1[i+N])] );
y[i+N] = y[i];
}

//calculate
double res = 0;
init(0,0,num-1);
int idx = events[0].second; double crtx = events[0].first; edge tempy = y[idx];
add(tempy.bcor, tempy.tcor, idx<N?1:-1, 0, 0, num-1);
for(int i=1; i<events.size(); i++){
idx = events[i].second; edge tempy = y[idx];
if(crtx<events[i].first){
res += (events[i].first-crtx)*sum(0, num-1, 0, 0, num-1);
crtx = events[i].first;
}
add(tempy.bcor, tempy.tcor, idx<N?1:-1, 0, 0, num-1);
}
cout<<"Test case #"<<++T<<endl;
printf("Total explored area: %.2f\n\n", res);
}

int main(){
while(cin>>N&&N!=0){
for(int i=0; i<N; i++){
cin>>x[i]>>ty[i]>>x[i+N]>>ty[i+N];
ty1[i] = ty[i]; ty1[i+N] = ty[i+N];
}
solve();
}
}```

Followed by: