oj.uz

답안 #633367

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633367 2022-08-22T08:25:53 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
5 / 100
 100 ms 10308 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
int n;
struct point
{
    int x,y,ang;
} v[100005],angle[100005];
bool comp(point a, point b)
{
    return a.y*b.x<a.x*b.y;
}
map<pii,int> nrm;
bool cmp(int a, int b)
{
    if(v[a].ang!=v[b].ang)
        return v[a].ang<v[b].ang;
    return v[a].y<v[b].y;
}
bool use[100005],spec[100005];
int aib[100005],times[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int cur=0;
bool iseq(point a, point b)
{
    return a.x==b.x&&a.y==b.y;
}
ll aria(point A, point B)
{
    ll rez=1LL*A.x*B.y-1LL*A.y*B.x;
    rez=abs(rez);
    return rez;
}
bool intersect(point A, point B, point C)
{
    if(iseq(A,C)||iseq(B,C))
        return 0;
 
    ll a1=B.y-A.y;
    ll b1=A.x-B.x;
    ll c1=-a1*A.x-b1*A.y;
 
    ll a2=C.y;
    ll b2=-C.x;
    ll c2=0;
 
    ld coef=a2*b1-a1*b2;
    if(coef==0)
        return 0;
    /*ld y=ld(-a2*c1)/coef;
    ld x=ld(-b2*y)/ld(a2);*/
    ld x=ld(c2*b1-c1*b2)/coef;
    ld y=ld(-c1-a1*x)/ld(b1);
    if(x>=min(A.x,B.x)&&x<=max(A.x,B.x)&&x<=C.x&&x>=0)
        if(y>=min(A.y,B.y)&&y<=max(A.y,B.y)&&y<=C.y&&y>=0)
            return 1;
    return 0;
}
bool checkgood(int i)
{
    if(cur==0)
        return 1;
    point a=v[cur];
    int lft=cur-1;
    if(lft<1)
        lft=n;
    point b=v[lft];
    if(intersect(a,b,v[i]))
        return 0;
    int rgt=cur+1;
    if(rgt>n)
        rgt=1;
    b=v[rgt];
    if(intersect(a,b,v[i]))
        return 0;
    return 1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x,y,0};
        int cmmdc=__gcd(x,y);
        x/=cmmdc;
        y/=cmmdc;
        angle[i]={x,y,0};
    }
    sort(angle+1,angle+n+1,comp);
   // cout<<'\n';
    for(int i=1;i<=n;i++)
    {
        pii a={angle[i].x,angle[i].y};
        nrm[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int cmmdc=__gcd(v[i].x,v[i].y);
        int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc;
        v[i].ang=nrm[{xa,ya}];
    }
    vector<int> ind;
    for(int i=1;i<=n;i++)
        ind.push_back(i);
    sort(ind.begin(),ind.end(),cmp);
    vector<int> sol;
    int nr=0;
    for(int i:ind)
    {
        nr++;
        bool good=checkgood(i);
        if(good)
        {
            cur=i;
            sol.push_back(i);
        }
    }
    sort(sol.begin(),sol.end());
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 3 ms 596 KB Output isn't correct
4 Correct 4 ms 724 KB Output is correct
5 Incorrect 14 ms 1364 KB Output isn't correct
6 Incorrect 14 ms 1364 KB Output isn't correct
7 Incorrect 28 ms 2348 KB Output isn't correct
8 Incorrect 10 ms 1132 KB Output isn't correct
9 Incorrect 8 ms 1104 KB Output isn't correct
10 Incorrect 13 ms 1364 KB Output isn't correct
11 Incorrect 15 ms 1372 KB Output isn't correct
12 Incorrect 22 ms 2428 KB Output isn't correct
13 Incorrect 41 ms 3392 KB Output isn't correct
14 Incorrect 44 ms 4428 KB Output isn't correct
15 Incorrect 66 ms 5304 KB Output isn't correct
16 Execution timed out 147 ms 10308 KB Time limit exceeded
17 Execution timed out 169 ms 10284 KB Time limit exceeded
18 Runtime error 57 ms 5136 KB Execution killed with signal 11
19 Runtime error 60 ms 5096 KB Execution killed with signal 11
20 Execution timed out 134 ms 8604 KB Time limit exceeded