QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#663513 | #9434. Italian Cuisine | inoader | TL | 0ms | 0kb | C++14 | 2.3kb | 2024-10-21 15:59:10 | 2024-10-21 15:59:10 |
answer
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
using namespace std;
const int N=1e6+10,INF=1e14,mod=998244353,M=2e5+10;
const double eps = 1e-8;
typedef pair<double,double> PII;
typedef pair<PII,int> PIII;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int qmi(int a,int k){
int res=1;
while(k){
if(k&1) res=res*a%mod;
a=a*a%mod;
k>>=1;
}
return res;
}
PII a[N];
PII operator-(PII t1,PII t2){
PII c={t1.x-t2.x,t1.y-t2.y};
return c;
}
PII operator+(PII t1,PII t2){
PII c={t1.x+t2.x,t1.y+t2.y};
return c;
}
int sign(double x){
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
return 1;
}
double cross(PII t1,PII t2){return t1.x*t2.y-t1.y*t2.x;}
double dot(PII a,PII b){
return a.x * b.x + a.y * b.y;
}
double get_length(PII a){
return sqrt(dot(a, a));
}
double distance_to_line(PII p, PII a, PII b){
PII v1 = b - a, v2 = p - a;
return fabs(cross(v1, v2) / get_length(v1));
}
double dts(PII p, PII a, PII b){
if (a == b) return get_length(p - a);
PII v1 = b - a, v2 = p - a, v3 = p - b;
if (sign(dot(v1, v2)) < 0) return get_length(v2);
if (sign(dot(v1, v3)) > 0) return get_length(v3);
return distance_to_line(p, a, b);
}
bool check(double p1,double p2){
if(sign(p1-p2)>=0) return true;//那就是可以
return false;
}
bool check1(PII x1,PII x2,PII x3,PII nei){
if(cross(x2-x1,nei-x1)<=0)return false;
if(cross(x3-x2,nei-x2)<=0) return false;
if(cross(x1-x3,nei-x3)<=0) return false;
return true;
}
void slove(){
int n;cin>>n;
int cx,cy,rr;cin>>cx>>cy>>rr;
PII dian={cx,cy};
double cr=rr;
for(int i=1;i<=n;i++){
int c1,c2;cin>>c1>>c2;
a[i]={c1,c2};
}
int l=1,r=1;
double area=0;
double ans=0;
for(int i=1;i<=n;i++){
if(l+2<=r){
int p=r%n;if(!p) p=n;
area-=fabs(cross(a[i]-a[i-1],a[p]-a[i-1]));
}
l=i,r=max(r,l+1);
int p1=(r+1)%n;if(!p1) p1=n;
int p2=(r)%n;if(!p2) p2=n;
while(check(dts(dian,a[l],a[p1]),cr)&&!check1(a[l],a[p2],a[p1],dian)){
area+=fabs(cross(a[p1]-a[l],a[p2]-a[l]));
r++;
p1=(r+1)%n;if(!p1) p1=n;
p2=(r)%n;if(!p2) p2=n;
}
ans=max(ans,area);
}
ans+=eps;
int q=ans*1;
cout<<q<<endl;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1;
// cin>>T;
while(T--) slove();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 5 1 1 1 0 0 1 0 5 0 3 3 0 5 6 2 4 1 2 0 4 0 6 3 4 6 2 6 0 3 4 3 3 1 3 0 6 3 3 6 0 3