Pagini recente » Cod sursa (job #2402621) | Cod sursa (job #1139499) | Cod sursa (job #836906) | Cod sursa (job #2637683) | Cod sursa (job #1091627)
#include<fstream>
#include<algorithm>
#include<deque>
using namespace std;
ifstream f("aria.in");
ofstream g("aria.out");
struct QQ{
double x;
double y;
double p;
};
bool cmp1(QQ i, QQ j){
if(i.x==j.x)
return i.y<j.y;
else
return i.x<j.x;
}
bool cmp2(QQ i, QQ j){
return i.p<j.p;
}
QQ a[100005];
deque<int> b;
int main(){
int n,i,j,x1,y1,xx1,xx2,k,q,w;
double m;
f>>n;
for(i=1; i<=n; ++i){
f>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1, cmp1);
xx1=a[n].x; xx2=a[n].y;
x1=a[1].x; y1=a[1].y;
for(i=2; i<=n; ++i){
a[i].p=(a[i].y-y1)/(a[i].x-x1);
}
sort(a+2, a+n+1,cmp2);
a[n+1]=a[1];
b.push_back(1);
b.push_back(2);
b.push_back(3);
if(n>3){
for(i=1; i<n-1; ++i){
k=b[b.size()-3];
q=b[b.size()-2];
w=b.back();
m=(a[q].y-a[k].y)*(a[w].x - a[q].x) - (a[w].y - a[q].y)*(a[q].x - a[k].x);
if(m>0){
b[b.size()-2]=b.back();
b.pop_back();
b.push_back(b.back()+1);
}
else{
b.push_back(b.back()+1);
}
}
}
double space=0;
for(i=1; a[i].x!=xx1 && a[i].y!=xx2; ++i){
space-=(a[b[i]].x-a[b[i-1]].x)/2*(a[b[i]].y + a[b[i-1]].y);
j=i;
}
for(i=j; i<b.size(); ++i){
space+=(a[b[i]].x-a[b[i+1]].x)/2*(a[b[i+1]].y + a[b[i+1]].y);
}
g<<space;
return 0;
}